计算机
启航官网 > 计算机 > 计算机备考 > 每日一练 > 文章
分享至

计算机考研每日一练:第八天

关键字: 计算机 考研 每日一练 时间:2019.01.16

平衡二叉树实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中,每当插入一个结点时,先检查是否因插入而破坏了树的平衡性,若是,则找出最小不平衡子树。在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。 下面讲解一个平衡二叉树构建过程的例子。现在又a[10] = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8}需要构建二叉排序树。在没有学习平衡二叉树之前,根据二叉排序树的特性,通常会将它构建成如下左图。虽然完全符合二叉排序树的定义,但是对这样高度达到8的二叉树来说,查找是非常不利的。因此,更加期望构建出如下右图的样子,高度为4的二叉排序树,这样才可以提供高效的查找效率。

现在来看看如何将一个数组构成出如上右图的树结构。 对于数组a的前两位3和2,很正常地构建,到了第个数“1”时,发现此时根结点“3”的平衡因子变成了2,此时整棵树都成了最小不平衡子树,需要进行调整,如下图图1(结点左上角数字为平衡因子BF值)。因为BF为正,因此将整个树进行右旋(顺时针),此时结点2成了根结点,3成了2的右孩子,这样三个结点的BF值均为0,非常的平衡,如下图图2所示。

然后再增加结点4,平衡因子没有改变,如上图图3。增加结点5时,结点3的BF值为-2,说明要旋转了。由于BF是负值,对这棵最小平衡子树进行左旋(逆时针旋转),如下图图4,此时整个树又达到了平衡。

继续增加结点6时,发现根结点2的BF值变成了-2,如下图图6所示。所以对根结点进行了左旋,注意此时本来结点3是结点3的左孩子,由于旋转后需要满足二叉排序树特性,因此它成了结点2的右孩子,如图7所示。

增加结点7,同样的左旋转,使得整棵树达到平衡,如下图8和9所示。

当增加结点10时,结构无变化,如图10所示。再增加结点9,此时结点7的BF变成了-2,理论上只需要旋转最小不平衡树7、9、10即可,但是,如果左旋转后,结点9变成了10的右孩子,这是不符合二叉排序树的特性的,此时不能简单的左旋。如图11所示。

仔细观察图11,发现根本原因在于结点7的BF是-2,而结点10的BF是1,也就是说,它们两个一正一负,符号并不统一,而前面的几次旋转,无论左还是右旋,最小不平衡子树的根结点与它的子结点符号都是相同的。这就是不能直接旋转的关键。 不统一,不统一就把它们先转到符号统一再说,于是先对结点9和结点10进行右旋,使得结点10成了9的右子树,结点9的BF为-1,此时就与结点7的BF值符号统一了,如图12所示。

这样再以结点7为最小不平衡子树进行左旋,得到如下图13。接着,插入8,情况与刚才类似,结点6的BF是-2,而它的右孩子9的BF是1,如图14,因此首先以9为根结点,进行右旋,得到图15,此时结点6和结点7的符号都是负,再以6为根结点左旋,最终得到最后的平衡二叉树,如图16所示。

通过这个例子,可以发现,当最小不平衡树根结点的平衡因子BF是大于1时,就右旋,小于-1时就左旋,如上例中的结点1、5、6、7的插入等。插入结点后,最小不平衡子树的BF与它的子树的BF符号相反时,就需要对结点先进行一次旋转以使得符号相同后,再反向旋转一次才能够完成平衡操作,如上例中结点9、8的插入时。

来源:启航考研 责任编辑:yulaoshi
热门活动