AVL

  1 #include <cmath>
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 template <typename T>
  7 class Node{
  8 public:
  9     T data;
 10     int count;
 11     Node<T> *L;
 12     Node<T> *R;
 13     Node():data(0), count(0), L(NULL), R(NULL){}
 14 };
 15 
 16 template <typename T>
 17 class AVLTree{
 18 private:
 19     Node<T> *insert(Node<T> *S, int data);
 20     Node<T> *SingleRotateLeft(Node<T> *S);
 21     Node<T> *SingleRotateRight(Node<T> *S);
 22 public:
 23     Node<T> *root;
 24     AVLTree():root(NULL){};
 25 
 26     int depth(Node<T> *S);
 27     Node<T> *check(int pos);
 28 
 29     void add(T data){root = insert(root, data);}
 30 };
 31 
 32 template <typename T> int AVLTree<T>::depth(Node<T> *S)
 33 {
 34     if(NULL == S)
 35         return 0;
 36     return depth(S->L) > depth(S->R) ? depth(S->L) + 1 : depth(S->R) + 1;
 37 }
 38 
 39 template <typename T> Node<T> *AVLTree<T>::check(int pos)
 40 {
 41     if(pos == 1)
 42         return root;
 43     Node<T> *parent = check(pos/2);
 44     if(NULL != parent)
 45         return pos%2 ? parent->R : parent->L;
 46     else
 47         return NULL;
 48 }
 49 
 50 template <typename T> Node<T> *AVLTree<T>::SingleRotateRight(Node<T> *S)
 51 {
 52     Node<T> *K = S->R;
 53     S->R = K->L;
 54     K->L = S;
 55     return K;
 56 }
 57 
 58 template <typename T> Node<T> *AVLTree<T>::SingleRotateLeft(Node<T> *S)
 59 {
 60     Node<T> *K = S->L;
 61     S->L = K->R;
 62     K->R = S;
 63     return K;
 64 }
 65 
 66 template <typename T> Node<T> * AVLTree<T>::insert(Node<T> *S, int data)
 67 {
 68     if(S == NULL)
 69     {
 70         S = new Node<T>();
 71         S->data = data;
 72         S->count = 1;
 73         if(root == NULL)
 74             root = S;
 75     }
 76     else if(S->data == data)
 77         S->count++;
 78     else if(data > S->data)
 79     {
 80         S->R = insert(S->R, data);
 81         if((depth(S->R) - depth(S->L)) == 2)
 82             if(data > S->R->data )
 83                 S = SingleRotateRight(S);
 84             else
 85             {
 86                 S->R = SingleRotateLeft(S->R);
 87                 S = SingleRotateRight(S);
 88             }
 89     }
 90     else
 91     {
 92         S->L = insert(S->L, data);
 93         if((depth(S->L) - depth(S->R)) == 2)
 94             if(S->L->data > data)
 95                 S = SingleRotateLeft(S);
 96             else
 97             {
 98                 S->L = SingleRotateRight(S->L);
 99                 S = SingleRotateLeft(S);
100             }
101     }
102     return S;
103 }
104 
105 template <typename T> ostream &operator<<(ostream &out,AVLTree<T> &R)
106 {
107     for(int i = 1; i < pow(2, R.depth(R.root)); i++)
108     {
109         if(R.check(i) == NULL)
110             cout<<i<<"\t"<<"NULL"<<endl;
111         else
112             cout<<i<<"\t"<<R.check(i)->data<<endl;
113     }
114     return out;
115 }
116 
117 int main()
118 {
119     AVLTree<int> t;
120     t.add(3);
121     t.add(2);
122     t.add(1);
123     t.add(4);
124     t.add(5);
125     t.add(6);
126     t.add(7);
127     t.add(10);
128     t.add(9);
129     t.add(8);
130     cout<<t<<endl;
131 }