平衡二叉树

（1）平衡二叉树（AVL树）的定义

1962年，Adelson  Velskii和Landis提出了AVL树（AVL tree）。

平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。

（2）结点的平衡因子balance

balance＝该结点的右子树高度-该结点的左子树高度

对于AVL树：balance=1。即balance只能取-1，0，1三者之一。换言之，若一棵二叉树上任一结点的平衡因子的绝对值都不大于1，则该树是就平衡二叉树。

（3）平衡化方法--平衡化旋转方法

Adelson  Velskii和Landis提出了一个动态地保持二叉排序树平衡的方法，其基本思想是：在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为AVL树。

所谓最小不平衡子树是指每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。

 （4）平衡二叉树的删除

如果被删除的结点x最多只有一个孩子，那么问题比较简单，将结点x从树中删去。因为结点x最多有一个孩子，我们可以简单的把x的双亲结点中原来指向x的指针改指到这个孩子结点上。如果结点x没有孩子，即是一个叶结点，则删除x后x双亲结点的相应指针应置为NULL。如果被删结点x即有左孩子又有右孩子，则首先搜索x在中序遍历中的直接前驱y（同样可以找直接后继），把结点y的内容传送给结点x，现在问题转移到删除结点y。

 

更多详细信息请参考如下网址：