什么是平衡二叉树（中）

什么是平衡二叉树（中）

在上一次跟大家介绍平衡二叉树的时候我们介绍了平衡二叉树的定义，以及如何去辨别什么是平衡二叉树，今天继续跟大家介绍平衡二叉树的实现原理。

同学们可以点击这里回顾之前的知识http://www.xastkj.cn/?mod=news_detail&id=94

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

为了能在讲解算法时轻松一些，我们先讲一个平衡二叉树构建过程的例子。假设我们现在有一个数组a[10]={3,2,1,4,5,6,7,10,9,8}需要构建二叉排序树。在没有学习平衡二叉树之前，根据二叉排序树的特性，我们通常会将它构建成如图5所示的样子。

虽然它完全符合二叉排序树的定义，但是对这样深度达到8的二叉树来说，查找是非常不利的。我们更期望能构建成如图6所示的样子，深度为4的二叉排序树才可以提供高效的查找效率。

那么现在我们就来研究如何将一个数组构建出图6的树结构。

(在以下图中，结点左上角数字为该结点的平衡因子BF值)

对于数组a[10]={3,2,1,4,5,6,7,10,9,8}的前两位3和2，我们很正常的构建。到了第3个数“1” 时，发现此时根结点”3“的平衡因子变成了2，此时整棵树都成了最小不平衡子树，因此需要调整，如下图7。因为BF值为正，因此我们将整个树进行右旋(顺时针旋转)，此时结点2成了根结点，3成了2的右孩子，这样三个结点的BF值均为0，非常的平衡，如下图8所示。

然后我们再增加结点4，如图9，平衡因子没有超出限定范围（-1，0，1）。

接下来增加结点5，如下图（图10），此时结点3的BF值为-2，说明要旋转了。由于BF是负值，所以我们对这颗最小平衡子树进行左旋（逆时针旋转），如图11，此时整个树又达到了平衡。

继续增加结点6，此时根结点2的BF值变成-2，如下图（图12）。所以我们对根结点进行左旋操作，注意此时原本结点3是结点4的左孩子，由于旋转后需要满足二叉排序树特性，因此它成了结点2的右孩子，如图13。

再增加结点7，同样进行左旋操作，使整棵树达到平衡，如图14和图15。

增加结点10，仍然平衡，如下（图16）。

再接下来增加结点9，此时结点7的BF变成-2，理论上来说我们只需要旋转最小平衡子树7，9，10即可，但是如果左旋转后，就会初选如下图（图17）虚线框出来的部分，这不符合二叉排序树的特性，此时就不能简单的左旋。

仔细观察图17，发现根本原因在于结点7的BF是-2，而结点10的BF是1，也就是说，它们符号不统一，而前面的几次旋转，无论是左旋还是右旋，最小不平衡子树的根结点与子节点的符号都是相同的。这就是不能直接旋转的原因。

不统一的话就把它们的符号先转统一，于是就如图17所示，先将结点9和结点10进行右旋，使结点10成为结点9的右子树，此时就与结点7的BF值符号统一了，如（图18）所示。

然后再以结点7为最小不平衡子树进行左旋，得到如下图（图19）。

接着插入8，情况与刚才类似，结点6的BF值为-2，而它的右孩子9的BF是1，如（图20），因此先以9为根结点，进行右旋，得到（图21）。

此时结点6和结点7的符号都是负，再以结点6为根结点左旋，最终得到最后的平衡二叉树，如下图（图22）所示。

根据以上的讲述，我们构建二叉排序树的过程中，每当插入一个节点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。

在保持二叉排序树特性的前提下，调整最小不平衡子树中各个节点之间的链接关系，进行对应的旋转，尤其注意当最小不平衡子树的BF值与它的子树的BF值符号相反时，就需要对结点先进行一次旋转使符号相同后，再反向旋转才能够完成平衡操作，使之成为新的平衡子树。

下一章将继续跟大家分享平衡二叉树实现算法。

文章参考《大话数据结构》