前面学习二叉查找树和二叉树的各种遍历，但是其查找效率不稳定(斜树)，而二叉平衡树的用途更多。查找相比稳定很多。(欢迎关注数据结构专栏)
AVL树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持。而且要保证它的深度是O(logN).
AVL的条件是左右树的高度差（平衡因子）不大于1；并且它的每个子树也都是平衡二叉树。
对于平衡二叉树的最小个数，n0=0;n1=1;nk=n(k-1)+n(k-2)+1;(求法可以类比斐波那契！)
难点：AVL是一颗二叉排序树，用什么样的规则或者规律让它能够在复杂度不太高的情况下实现动态平衡呢？
如果简单的以单节点看，大致有上面四种情形，并且他们的最后结果也是有的有所相近。只是：上下会变动。该在左面的还在左面，改在右面的还在右面。
这只是针对在底部，对于可能出现的平衡要首先搞清楚：
所以针对四种不平衡，可能出现在底部，也可能出现在头，也可能出现在某个中间节点导致不平衡。 而我们只需要研究其首次不平衡点，解决之后整棵树即继续平衡。当然，在实际解决肯定会带上递归的思想解决问题。 # 四种平衡旋转方式 RR平衡旋转(左单旋转)
出现这种情况的原因是节点的右侧的右侧较深这时候不平衡节点需要左旋。再细看过程。
再左旋的过程中，root(oldroot)节点下沉，中间节点(newroot)上浮.而其中中间节点(newroot)的右侧依然不变。
它上浮左侧所以需要指向根节点(oldroot)(毕竟一棵树)。但是这样newroot原来左侧节点H空缺。而我们需要仍然让整个树完整并且满足二叉排序树的规则。
而刚好本来oldroot右侧指向newroot变成oldroot被newroot左侧指向。所以oldroot右侧空缺，刚好这个位置满足在oldroot的右侧。在newroot的左侧。.所以我们将H插入在这个位置。
其中H可能为NULL。不过不影响操作！
而左旋的代码可以表示为： private node getRRbanlance(node oldroot) {//右右深，需要左旋 // TODO Auto-generated method stub node newroot=oldroot.right; oldroot.right=newroot.left; newroot.left=oldroot; oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1; newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原来的root的高度需要从新计算 return newroot; } LL平衡旋转(右单旋转)
而右旋和左旋相反，但是思路相同，根据上述进行替换即可！
代码： private node getLLbanlance(node oldroot) {//LL小，需要右旋转 // TODO Auto-generated method stub node newroot=oldroot.left; oldroot.left=newroot.right; newroot.right=oldroot; oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1; newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原来的root的高度需要从新金酸 return newroot; } RL平衡旋转(先右后左双旋转)
产生不平衡的条件原因是：
root节点右侧左侧节点的深度高些，使得与左侧的差大于1.这个与我们前面看到的左旋右旋不同的是因为它的结构不能直接变一下就可以完成。