查找树
平衡二叉树先是一颗查找树，所以先从查找树的性质讲起。
查找树的递归定义是，每个节点的左孩子值不大于它、右孩子不小于它，由此构成的二叉树即为查找树。据此性质，在插入或查找时，从根节点向下逐一比较，即可找到相应的插入或查找的位置。
查找树
在极端情况下，比如连续插入依次递增或递减的节点，查找树将退化成链表，复杂度从o(lgn)退化成o(n)，为避免这种情况，我们需要在查找树的基础上加上限制条件…
退化成链表的情况
平衡二叉树
平衡二叉树有多种，只因各自的限制条件不尽相同，这里只讲AVL树。
对AVL树而言，每个节点左右孩子的树高差不超过1，否则需要旋转树达到平衡。
平衡二叉树
在假定除根节点外的每个节点都达到平衡的情况下，该树只有四种不平衡的状态:
i.左子树比右子树高（默认都是高2个单位以上的，下同），且左子树的左树高
ii.右子树比左子树高，且右子树的右树高
iii.左子树比右子树高，且左子树的右树高
iv.右子树比左子树高，且右子树的左树高
平衡操作
我们分情况讨论，并使树重新达到平衡。
i.右旋
情况1
对于情况1，我们仅仅需要一次右旋操作即可，大家可以把树想得十分柔软，在重力的作用下自然下垂，然后我们把B节点用力提起，这棵树就成了下图的样子…
右旋后
ii.左旋
情况2
情况2与情况1是对称的，进行的操作也类似，只需一次左旋操作即可使树重新达到平衡。
左旋后
iii.左右双旋
情况3
情况3比前面两种略微复杂，需要两次旋转操作才能使树重新达到平衡。我们先将目光移到A节点的左树，然后以该子树为基础做左旋操作，如情况2所示，于是我们得到下图，
左子树左旋
由于根节点左子树本来就是平衡的，所以左旋之后依然平衡，不过此时左子树的左树已经比右树高了，于是我们将情况3转化成了情况1，再对整颗树做一次右旋操作即可。
整树右旋
iv.右左双旋
情况4
情况4与情况3对称，也是先通过右旋将情况4转换成情况2，再左旋重新达到平衡，所以不再赘述。
插入
如果树不存在节点，那么新节点为根节点，否则依照查找树的性质从根节点开始向下比较，直至到达末尾节点，此时新节点作为树的叶子节点，然后从新节点开始向上回溯，平衡每个回溯的节点，直到将整颗树平衡。插入前的树是平衡的，易证每个回溯节点的左右子树都是平衡的，参考上节平衡二叉树的四种基本情况即可平衡回溯节点，从而当回溯到根节点时，我们即可平衡整颗二叉树。
删除
在删除之前，我们需要依照查找树的性质定位到删除节点，即查找操作，找到删除节点后，如果为叶子节点，直接删除，否则从左子树或者右子树中选择一个替换节点，替代删除节点的位置，一般选择树高最大的那颗。如果是左子树，那么寻找子树值最大的节点，否则寻找右子树最小的节点作为替换节点，这是为了避免破坏查找树的性质而做出的必然选择。值得一提的是，在取下替换节点时，如果替换节点存在子树，这颗子树的根节点应当替代替换节点的位置。
我们使用替换节点替换删除节点的位置后，就应该从替换节点（替换节点原来的父节点）的父节点开始平衡二叉树了。与插入时平衡二叉树类似，由于删除之前就是平衡的，所以向上回溯时节点的子树都是平衡的，最后回溯至根节点，我们即可重新平衡整颗二叉树。
参考资料
为了解平衡二叉树，我从网上参考了一些事例，感觉说的不是很清楚，几乎都只是摆出了针对四种情况的旋转操作，并没有指出它们和插入删除之间的联系，让人觉得很迷惑，最后在家翻看了之前的教材（清华大学出版的《数据结构》）才明白了一点，那个将树提起来的想法就是参考这本书的描述，我觉得非常形象易懂…最后给出我实现此树的源码:
网友评论