平衡二叉搜索树(AVL)

从二叉搜索树BST中可以看出，如果一个数据在'很深'的节点处保存、对于搜索的开销就会很大，能不能调整一下树的结构，让查询所有的数据的时间差不多平衡。

平衡二叉树AVL解释: 这两人的 Adelson-Velsky 和 E.M. Landis的名字缩写，在他们发表的文章'An algorithm for the organization of information'提及该算法。

平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉树查询来说，时间上稳定了很多。


平衡二叉树实现的大部分过程和二叉查找树是一样的，区别就在于插入和删除之后要写一个旋转[算法]去维持平衡，维持平衡需要借助一个节点高度的属性。

AVL树的旋转规律

1. LL型

       平衡二叉树某一节点的左孩子的左子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向右旋转一次即可，如图所示，原A的左孩子B变为父结点，A变为其右孩子，而原B的右子树变为A的左子树，注意旋转之后Brh是A的左子树:(淡红色尾部为要添加子树的节点)

2. RR型

平衡二叉树某一节点的右孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向左旋转一次即可，如图所示，原A右孩子B变为父结点，A变为其左孩子，而原B的左子树Blh将变为A的右子树:

3. LR型

平衡二叉树某一节点的左孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时需要旋转两次，仅一次的旋转是不能够使二叉树再次平衡。如图所示，在B节点按照RR型向左旋转一次之后，二叉树在A节点仍然不能保持平衡，这时还需要再向右旋转一次：

4. RL型

平衡二叉树某一节点的右孩子的左子树上插入一个新的节点，使得该节点不再平衡。同样，这时需要旋转两次，旋转方向刚好同LR型相反：

java实现:http://blog.csdn.net/zxman660/article/details/7940190