AVL树是最早发明的自平衡二叉搜索树，以其发明者G.M. Adelson-Velsky和E.M. Landis命名。
由于AVL树中为任何节点的两个子树的高度最大差别为一，因此也称为高度平衡树。
查找、插入和删除为平均，最坏情况为o(logn )，插入和删除可能需要通过一次或多次树旋转来恢复此树的平衡。
如下图所示，左侧树为AVL树，操作效率明显高于右侧树。
插入新节点可能会导致AVL树失去平衡，应该如何调整和重新平衡呢？
首先，必须考虑所有不平衡的情况。
不平衡时：考虑3层，分为4类的新节点的插入位置有很多可能性，如何对不平衡时进行分类，或者需要考虑多大范围？
想想三楼的高度就可以了。
在下图中，假设插入1次根(10 )的左儿子)6)的左子树)4)，则无论插入位置是左)插入2 )还是右)插入5 )，都可以通过1次右转)顺时针)实现平衡。
所以对根的左儿子的左子树进行一次插入后破坏平衡，都可归类为“左左”情况。
基于这样的想法，假设需要再平衡的节点为，则可以将所有可能的情况分为4类。
1 .在的左儿子的左子树中插入一次(左) )。
2 .在的左儿子的右子树中插入一次(左右) ) ) ) ) ) ) ) )。
3 .在右边儿子左边的子树中插入一次(左右) )。
4 .插入右边儿子右边子树一次(右边) )。
为了对称性，1、4和2、3是两组镜像问题，重点解决单侧问题即可。 想想左边和右边的情况吧。
(左)速记方法)犯了两次左倾错误，需要用右法纠正。
当在子树T0中添加新节点时，根节点g的左右子树失去平衡，g-T0比g-T3的深度多2。
需要对g节点执行一次右旋转。 具体步骤如下。
g.left=p.right； //g的左子代指向p的右子代的p.right=g； //g变为p的右边子root=p； //p作为新的根
LR )左右)速记方法：犯一次左倾错误和一次右倾错误时，先左旋纠正，再右旋纠正左倾。
当在子树T2中添加新节点时，根节点g的左右子树失去平衡，g-T2比g-T3的深度多2。
此时，首先是3358www.Sina.com/(p(虽然没有破坏以p为根据的树的平衡，但这是必要的准备工作)，具体步骤如下。
p.right=n.left； //p的左子代指向n的右子代的n.left=p； //p为n的左子根=N； //n作为子树新的根经过左旋后，g的左子左子树“太重”失去了平衡，可以回到“左”的情况。 (设想新节点的插入位置为子树T1，左旋转后也为"左"的情况)
可以通过对p节点执行一次左旋转恢复平衡。
g.left=p.right； //g的左子代指向p的右子代的p.right=g； //g变为p的右边子root=p； //p作为新的根RR (右)左镜像问题。
对g节点执行一次右旋转(逆时针方向) :
g.right=p.left； //g的右子代指向p的左子代的p.left=g； //g变为p的左子root=p； //p作为新的根RL (左右)左右的镜像问题。
首先是对g执行一次左旋
p.left=n.right； //p的右边子代指向n的左边子代的n.right=p； //p为n的右边子root=n； //n作为子树的新根可以在对p节点执行一次右旋转中重新平衡：
g.right=p.left； //g的右子代指向p的左子代的p.left=g； //g变为p的左子root=p； //p作为新的根代码在这里参照ssddm的代码，输入一系列的节点值，作为根的值输出。
# includeiostreamusingnamespacestd； struct node { int val； struct node *left，*right； (； node*rotateleft(node*root ) { node *t=root-right； 根权限=t-left； t-left=路线； 返回t； }node*rotateright(node*root ) { node *t=root-left； 根=t-right； t-right=root； 返回t； } node * rotate left right (node * root ) root-left=rotateleft ) root-left )； returnrotateright(root； } node * rotaterightleft (node * root ) root-right=rotateright ) root-right )； 返回旋转左(root； }intgetheight(node*root ) if ) root==null ) return 0； returnmax (getheight (根)、getheight (根)权) 1； }node*insert(node*root，int val ) if ) root==null ) { root=new node； 根val=val； 根- left=根- right=null； }elseif(valroot-val ) root-left=insert (root-left，val )； -getheight (根-左)-getheight (根-右)==2)根=val根-左- val？ 根(root ) :根(rotate left right )根； } else { root-right=insert (root-right，val )； getheight (root-left )-getheight (root-right )=-2 ) root=val root-right-val？ 旋转左(root ) :旋转右(rotaterightleft )根； } return root； (}int main ) ) { int n，val； scanf('%d '，n )； node * root=空； for(intI=0； i n； I ) Scanf('%d '，val )； root=insert(root，val )； }printf('%d”，root-val )； 返回0； }参考资料平衡二叉树详细解
平衡二叉搜索树
AVL树的详细实现
1066.rootofAVLtree(25 )-PAT甲级真题