AVL树是一种自平衡二叉查找树。它的平衡因子等于它的左子树的高度减去它的右子树的高度。只有平衡因子等于1，0，-1的结点是平衡的，不平衡的结点需要通过旋转来保持平衡。因此，在AVL树中任何结点的两个子树的高度差的最大值为1。

google到了一篇代码很简洁易懂的文章，将其中的代码整理了一下：

1 //AVL Tree  2 #include 
     
        3 #include 
      
         4 using namespace std;  5   6 typedef int Type;  7   8 struct avl_node{  9     Type data; 10     avl_node *lchild, *rchild; 11 }*root; 12  13  14 class avlTree{ 15 public: 16     avlTree(){ 17         root=NULL; 18     } 19  20     ~avlTree(){ 21         delete_tree(root); 22     } 23  24     void delete_tree(avl_node *node){ 25         if(node->lchild!=NULL){ 26             delete_tree(node->lchild); 27         } 28         if(node->rchild!=NULL){ 29             delete_tree(node->rchild); 30         } 31         delete node; 32         node=NULL; 33     } 34  35     //get height of a node 36     //the height of one single node is 1 (not 0) 37     int height(avl_node* node){ 38         if(node==NULL) return 0; 39         int left_h=height(node->lchild); 40         int right_h=height(node->rchild); 41         return max(left_h,right_h)+1; 42     } 43      44     //get difference of height of the node's left tree and right tree 45     //node will not be NULL 46     //calculated by left-right 47     int diff(avl_node* node){ 48         int left_h=height(node->lchild); 49         int right_h=height(node->rchild); 50         return left_h-right_h; 51     } 52      53     avl_node* RR_rotation(avl_node* head){ 54         avl_node* temp=head->rchild; 55         head->rchild=temp->lchild; 56         temp->lchild=head; 57         return temp; 58     } 59      60     avl_node* LL_rotation(avl_node* head){ 61         avl_node* temp=head->lchild; 62         head->lchild=temp->rchild; 63         temp->rchild=head; 64         return temp; 65     } 66      67     avl_node* LR_rotation(avl_node* head){ 68         head->lchild=RR_rotation(head->lchild); 69         return LL_rotation(head); 70     } 71      72     avl_node* RL_rotation(avl_node* head){ 73         head->rchild=LL_rotation(head->rchild); 74         return RR_rotation(head); 75     } 76      77     //recursively check and keep the tree balanced 78     avl_node* balance(avl_node* head){ 79         int bal_factor=diff(head); 80         //balance factor==2 81         if(bal_factor>1){ 82             if(diff(head->lchild)>0){ 83                 head=LL_rotation(head); 84             } 85             else{ 86                 head=LR_rotation(head); 87             } 88         } 89         //balance factor=-2 90         else if(bal_factor<-1){ 91             if(diff(head->rchild)>0){ 92                 head=RL_rotation(head); 93             } 94             else{ 95                 head=RR_rotation(head); 96             } 97         } 98         return head; 99     }100     101     avl_node* insert(avl_node* root, Type value){102         if(root==NULL){103             root=new avl_node;104             root->data=value;105             root->lchild=NULL;106             root->rchild=NULL;107             return root;108         }109         else if(value
       
        data){110             root->lchild=insert(root->lchild,value);111             root=balance(root);112         }113         else if(value>root->data){114             root->rchild=insert(root->rchild,value);115             root=balance(root);116         }117         return root;118     }119     120     //an interesting way to display the tree horizontally121     void display(avl_node* cur, int level){122         if(cur!=NULL){123             display(cur->rchild, level+1);124             cout<
        
          ";127             }128             for(int i=0;i
         
          data;132             display(cur->lchild, level+1);133         }134     }135     136     void preorder(avl_node* cur){137         if(cur==NULL) return;138         cout<
          
           data<<" ";139 preorder(cur->lchild);140 preorder(cur->rchild);141 }142 143 void inorder(avl_node* cur){144 if(cur==NULL) return;145 inorder(cur->lchild);146 cout<
           
            data<<" ";147 inorder(cur->rchild);148 }149 150 void postorder(avl_node* cur){151 if(cur==NULL) return;152 postorder(cur->lchild);153 postorder(cur->rchild);154 cout<
            
             data<<" ";155 }156 };157 158 159 160 //for testing161 int main()162 {163 int choice;164 Type item;165 avlTree avl;166 while (1)167 {168 cout<<"\n---------------------"<
             
              >choice;179 switch(choice)180 {181 case 1:182 cout<<"Enter value to be inserted: ";183 cin>>item;184 root = avl.insert(root, item);185 break;186 case 2:187 if (root == NULL)188 {189 cout<<"Tree is Empty"<
             
            
           
          
         
        
       
      
     

 

测试结果和原文请见：