avltree.hpp

数据结构课程程序

/**********************************************************/
/*              Programmed by Gerard Monells              */
/*               [e-mail]                */
/**********************************************************/

#ifndef _AVLTREE_HPP
#define _AVLTREE_HPP

#include <iostream>
typedef unsigned int uint;

template <typename T>
class AVLtree {

public:
  AVLtree();
  AVLtree(const AVLtree<T>& a);
  AVLtree<T>& operator=(const AVLtree<T>& a);
  ~AVLtree();
  void add_item(T x);
  bool search(T x);
  uint size();
  void preorder();
  void inorder();
  void postorder();

private:
  struct node {
    node(T x, node* l, node* r, uint h) {
      item = x;
      left = l;
      right = r;
      height = h;
    }
    T item;
    node* left;
    node* right;
    uint height;
  };

  node* root;
  uint num_nodes;

  static AVLtree<T>::node* AVLtree<T>::copy_nodes(node *n);
  static void AVLtree<T>::destroy_nodes(node *n);
  static AVLtree<T>::node* AVLtree<T>::add_node(node* n, T x);
  static uint AVLtree<T>::max(uint a, uint b);
  static uint AVLtree<T>::height(node* n);
  static AVLtree<T>::node* AVLtree<T>::rotate_left(node* n);
  static AVLtree<T>::node* AVLtree<T>::rotate2_left(node* n);
  static AVLtree<T>::node* AVLtree<T>::rotate_right(node* n);
  static AVLtree<T>::node* AVLtree<T>::rotate2_right(node* n);
  static bool AVLtree<T>::search(node* n, T x);
  static void AVLtree<T>::preorder(node* n);
  static void AVLtree<T>::inorder(node* n);
  static void AVLtree<T>::postorder(node* n);
};

template <typename T>
AVLtree<T>::AVLtree() {
  root = NULL;
  num_nodes = 0;
}

template <typename T>
AVLtree<T>::AVLtree(const AVLtree<T>& a) {
  root = copy_nodes(a.root);
  num_nodes = a.num_nodes;
}

template <typename T>
AVLtree<T>& AVLtree<T>::operator=(const AVLtree<T>& a) {
  destroy_nodes(root);
  root = copy_nodes(a.root);
  num_nodes = a.num_nodes;
}

template <typename T>
AVLtree<T>::~AVLtree() {
  destroy_nodes(root);
}

template <typename T>
void AVLtree<T>::add_item(T x) {
  root = add_node(root, x);
  num_nodes++;
}

template <typename T>
bool AVLtree<T>::search(T x) {
  return search(root, x);
}

template <typename T>
uint AVLtree<T>::size() {
  return num_nodes;
}

template <typename T>
void AVLtree<T>::preorder() {
  preorder(root);
}

template <typename T>
void AVLtree<T>::inorder() {
  inorder(root);
}

template <typename T>
void AVLtree<T>::postorder() {
  postorder(root);
}

template <typename T>
AVLtree<T>::node* AVLtree<T>::copy_nodes(node *n) {
  if (n == NULL) return NULL;
  node* p;
  node* l;
  node* r;
  l = copy_nodes(n->left);
  r = copy_nodes(n->right);
  p = new node(n->item, l, r, n->height);
  return p;
}

template <typename T>
void AVLtree<T>::destroy_nodes(node *n) {
  if (n != NULL) {
    destroy_nodes(n->left);
    destroy_nodes(n->right);
    delete n;
  }
}

template <typename T>
AVLtree<T>::node* AVLtree<T>::add_node(node* n, T x) {
  if (n == NULL) {
    node* p;
    p = new node(x, NULL, NULL, 1);
    return p;
  } else {
    if (x < n->item) {
      n->left = add_node(n->left, x);
      if (height(n->left) - height(n->right) == 2) {
        if (x < n->left->item) {
          n = rotate_right(n);
        } else {
          n = rotate2_right(n);
        }
      }
    } else {
      n->right = add_node(n->right, x);
      if (height(n->right) - height(n->left) == 2) {
        if (x >= n->right->item) {
          n = rotate_left(n);
        } else {
          n = rotate2_left(n);
        }
      }
    }
    n->height = 1 + max(height(n->left), height(n->right));
    return n;
  }
}

template <typename T>
uint AVLtree<T>::max(uint a, uint b) {
  if (a > b) return a;
  return b;
}

template <typename T>
uint AVLtree<T>::height(node* n) {
  if (n == NULL) return 0;
  return n->height;
}

template <typename T>
AVLtree<T>::node* AVLtree<T>::rotate_left(node* n) {
  node* p;
  p = n->right;
  n->right = p->left;
  p->left = n;
  n->height = 1 + max(height(n->left), height(n->right));
  p->height = 1 + max(height(p->left), height(p->right));
  return p;
}

template <typename T>
AVLtree<T>::node* AVLtree<T>::rotate2_left(node* n) {
  n->right = rotate_right(n->right);
  n = rotate_left(n);
  return n;
}

template <typename T>
AVLtree<T>::node* AVLtree<T>::rotate_right(node* n) {
  node* p;
  p = n->left;
  n->left = p->right;
  p->right = n;
  n->height = 1 + max(height(n->left), height(n->right));
  p->height = 1 + max(height(p->left), height(p->right));
  return p;
}

template <typename T>
AVLtree<T>::node* AVLtree<T>::rotate2_right(node* n) {
  n->left = rotate_left(n->left);
  n = rotate_right(n);
  return n;
}

template <typename T>
bool AVLtree<T>::search(node* n, T x) {
  if (n == NULL) return false;
  if (n->item == x) return true;
  if (n->item > x) {
    return search(n->left, x);
  } else {
    return search(n->right, x);
  }
}

template <typename T>
void AVLtree<T>::preorder(node* n) {
  if (n != NULL) {
    cout << n->item << " ";
    preorder(n->left);
    preorder(n->right);
  }
}

template <typename T>
void AVLtree<T>::inorder(node* n) {
  if (n != NULL) {
    inorder(n->left);
    cout << n->item << " ";
    inorder(n->right);
  }
}

template <typename T>
void AVLtree<T>::postorder(node* n) {
  if (n != NULL) {
    postorder(n->left);
    postorder(n->right);
    cout << n->item << " ";
  }
}

#endif