1 #include 
     
        2 #include 
      
         3   4 using namespace std;  5   6 template 
       
          7 class Node{  8 public:  9     T data; 10     int count; 11     Node
        
          *L; 12     Node
         
           *R; 13     Node():data(0), count(0), L(NULL), R(NULL){} 14 }; 15  16 template 
          
            17 class AVLTree{ 18 private: 19 Node
           
             *insert(Node
            
              *S, int data); 20 Node
             
               *SingleRotateLeft(Node
              
                *S); 21 Node
               
                 *SingleRotateRight(Node
                
                  *S); 22 public: 23 Node
                 
                   *root; 24 AVLTree():root(NULL){}; 25 26 int depth(Node
                  
                    *S); 27 Node
                   
                     *check(int pos); 28 29 void add(T data){root = insert(root, data);} 30 }; 31 32 template 
                    
                      int AVLTree
                     
                      ::depth(Node
                      
                        *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 
                       
                         Node
                        
                          *AVLTree
                         
                          ::check(int pos) 40 { 41 if(pos == 1) 42 return root; 43 Node
                          
                            *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 
                           
                             Node
                            
                              *AVLTree
                             
                              ::SingleRotateRight(Node
                              
                                *S) 51 { 52 Node
                               
                                 *K = S->R; 53 S->R = K->L; 54 K->L = S; 55 return K; 56 } 57 58 template 
                                
                                  Node
                                 
                                   *AVLTree
                                  
                                   ::SingleRotateLeft(Node
                                   
                                     *S) 59 { 60 Node
                                    
                                      *K = S->L; 61 S->L = K->R; 62 K->R = S; 63 return K; 64 } 65 66 template 
                                     
                                       Node
                                      
                                        * AVLTree
                                       
                                        ::insert(Node
                                        
                                          *S, int data) 67 { 68 if(S == NULL) 69 { 70 S = new Node
                                         
                                          (); 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 
                                          
                                            ostream &operator<<(ostream &out,AVLTree
                                           
                                             &R)106 {107 for(int i = 1; i < pow(2, R.depth(R.root)); i++)108 {109 if(R.check(i) == NULL)110 cout<
                                            <<"\t"<<"NULL"<
                                             
                                              data<
                                              

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<

<