对于搜索树来说，不同的插入顺序会导致树的结构不一样，最终导致查找效率不一样。经过计算，发现左右子树比较平衡的树查找效率比较高。
平衡因子（Balance Factor，BF） BF(T)=hl-hr ，hl、hr表示树T的左右子树的高度。
平衡二叉树（Binary Balanced Tree) (AVL)树 空树，或者左右子树高度相差不超过1 ，即|BF(T)|<1。
平衡二叉树在删除插入中，其平衡性可能会被破坏，下面我们就平衡二叉树的调整进行讨论：
一、RR旋转
新节点插入在不平衡“发现者”的左子树的左子树上。
如图，当节点插入在B的左子树上（可以在B的左子树上的任何位置，也可以作为B的左子树），A的平衡因子大于1，平衡性破坏，以A做为“发现者”，进行RR旋转。
我们将发现者A的左儿子B（这里B是一定存在的）作为新的根节点，A比B大作为B的新右儿子，原来的B的右子树因为在A的左子树下，比A小，所以现在作为A的左儿子。
二、LL旋转
与RR旋转同理，新节点插入在不平衡“发现者”的右子树的右子树上。
如图，当节点插入在B的右子树上（可以在B的右子树上的任何位置，也可以作为B的右子树），A的平衡因子小于-1，平衡性破坏，以A作为“发现者”，进行LL旋转。
我们将发现者A的右儿子B（这里B是一定存在的）作为新的根节点，A比B小作为B的新左儿子，原来的B的左子树因为在A的右子树下，比A大，所以现在作为A的右儿子。
三、LR旋转
新节点插入在不平衡“发现者”的左子树的右子树上。
如图，当节点插入在B的右子树上（可以在B的右子树上的任何位置，也可以作为B的右子树），A的平衡因子大于1，平衡性破坏，以A作为“发现者”，进行LR旋转。
我们A、B、C中的中间值C作为新的根节点。A比C大作为C的新右儿子，B比C小作为C的新左儿子。原来C的左子树在B的右子树下，比B大，作为B的右子树，原来的C的右儿子在A的左子树下，作为A的左子树。
四、RL旋转
同LR旋转，新节点插入在不平衡“发现者”的右子树的左子树上。
如图，当节点插入在B的左子树上（可以在B的右子树上的任何位置，也可以作为B的右子树），A的平衡因子小于-1，平衡性破坏，以A作为“发现者”，进行RL旋转。
我们A、B、C中的中间值C作为新的根节点。A比C小作为C的新左儿子，B比C大作为C的新右儿子。原来C的右子树在B的左子树下，比B小，作为B的新左子树；原来的C的左儿子在A的右子树下，作为A的新右子树。
五、代码实现
1.求树高：树高是树中节点的最大层数。这里可以用递归先求左右子树的树高，取最大值+1，及当前树的树高。
2.RL旋转可以这这么实现：将B做RR旋转，这样麻烦节点（破坏平衡性的节点）就从左子树的右子树旋转到了左子树的左子树，再做LL旋转即可。
3.插入的时候，怎么知道新节点的下一个递归去了下个节点的左子树还是右子树？用数值进行比较就能判断。
1 struct AVLNode{ 3 int data; 4 AVLNode* left; 5 AVLNode* right; 6 }; 7 8 AVLNode* LL( AVLNode* u) 9 { 10 AVLNode* t=u->left; 11 u->left=t->right; 12 t->right=u; 13 return t; 14 } 15 AVLNode* RR( AVLNode* u) 16 { 18 AVLNode* t=u->right; 19 u->right=t->left; 20 t->left=u; 21 return t; 22 } 23 AVLNode* LR( AVLNode* u) 24 { 26 AVLNode* t=u->left->right; 27 AVLNode* tb=u->left; 28 tb->right=t->left; 29 u->left=t->right; 30 t->left=tb; 31 t->right=u; 32 return t; 33 } 34 AVLNode* RL( AVLNode* u) 35 { 37 AVLNode* t=u->right->left; 38 AVLNode* tc=u->right; 39 tc->left=t->right; 40 u->right=t->left; 41 t->right=tc; 42 t->left=u; 43 return t; 44 45 } 46 int getHeight( AVLNode* u) 47 { 48 if( u==NULL ) return 0; 49 return max( getHeight(u->left) ,getHeight(u->right) )+1; 50 } 51 AVLNode* Insert( AVLNode* u,int x) 52 { 53 if(u==NULL) 54 { 55 u=(AVLNode*)malloc( sizeof(struct AVLNode)); 56 u->left=u->right=NULL; 57 u->data=x; 58 }else{ 59 60 if( x < u->data ) 61 { 62 u->left=Insert( u->left, x ); 63 64 if( getHeight(u->left) - getHeight(u->right) > 1 ) 65 { 66 if( x < u->left->data ) u=LL(u); 67 else u=LR(u); 68 } 69 70 } 71 else 72 { 73 u->right=Insert(u->right,x); 74 75 if( getHeight(u->left) - getHeight(u->right) < -1 ) 76 { 77 if( x > u->right->data ) u=RR(u); 78 else u=RL(u); 79 } 80 81 } 82 } 83 return u; 84 85 }