侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

平衡二叉树的构建实现过程演示

kaixindeken
2021-04-22 / 0 评论 / 0 点赞 / 60 阅读 / 2,350 字

实例演示

在开始之前,我们先通过一个对比来加强理解,在没有介绍平衡二叉树之前,你可能会构造出这样的一棵二叉树:

1.jpeg

虽然这也是一棵二叉排序树,但是层数达到 8,显然可以通过平衡二叉树来降低层数,提高性能,如果把它转化为平衡二叉树,会是这个样子:

1.jpeg

层数降低了一半,变成了 4 层,显然性能要比之前要高。那么这个平衡二叉树是怎么构建的呢?假设插入节点的顺序是{3,2,1,4,5,6,7,10,9,8},两个节点之前不用考虑,我们从第三个节点开始分析:

1.jpeg

插入第三个节点 1 时,左子树高度是 2,右子树高度是 0,高度差的绝对值是 2,不符合平衡二叉树的要求,需要把以 3 为根节点的子树进行右旋,到右图那个样子,左右子树高度差为 0,符合平衡二叉树要求,完成调整。同理,插入第四个节点 4 的时候,左右子树高度为 -1,符合平衡二叉树要求,继续插入第五个节点,此时又不符合平衡二叉树的要求了,这个时候右子树比较高,需要左旋:

1.jpeg

旋转的时候以最小不平衡子树为单位,此时最小的不平衡子树是 3、4、5 节点构成的子树,我们以 4 为中心进行左旋,将树结构调整为右图所示的样子,满足了平衡二叉树的要求,停止调整。注意到我们每次新增节点的时候,会调整以每个节点为根节点的左右子树的高度差,然后从最小子树开始进行调整,直到以每个节点为根节点的子树符合平衡二叉树的要求,这样整棵树就符合平衡二叉树的要求了。

继续增加节点,当插入节点 6 时,发现根节点 2 上维护的高度差值为 -2,又不满足平衡二叉树了,这个时候,需要以 2 为中心对树进行左旋,最终调整为右图所示的结构满足平衡二叉树要求(右子树中旋转到根节点的节点对应子树需要移到旋转后二叉树的左子树中):

1.jpeg

继续增加节点 7,此时以 5 为根节点的最小子树不满足平衡二叉树的要求了,需要左旋:

1.jpeg

继续增加节点 10,满足平衡二叉树要求,再插入节点 9,又不满足了:

1.jpeg

这个时候,情况有点微妙,不像我们之前旋转的时候时候处理情况都比较简单,单纯左转满足不了需求,需要先将以 10 作为根节点的子树做一次右转,再将以 7 为根节点的子树做一次左转,让这棵不平衡子树转化为平衡子树:

1.jpeg

这样整棵二叉树就满足平衡二叉树的要求了:

1.jpeg

最后,我们插入节点 8,此时情况和刚才类似,这个时候,我们以 9 为根节点对子树进行右旋,再以 6 为根节点对子树进行左旋,最终达到平衡状态:

1.jpeg

总结一下,大体的思路是平衡因子 BF 的值大于 1 时,右旋,小于 -1 时左旋,如果最小不平衡子树的 BF 值和其子树的 BF 值符号相反时,需要先将子树进行旋转使两者 BF 值符号相同,再旋转最小不平衡子树。我们将单纯的左旋、右旋叫做单旋处理,将需要两次旋转处理的操作叫做双旋处理。

算法复杂度

二叉排序树的插入、删除、查找时,最理想的情况下,时间复杂度是 O(logn),而平衡二叉树就是这种理想情况,虽然平衡二叉树性能是最好的,也是最稳定的,但是这套算法实现起来比较复杂,每次插入节点和删除节点都需要判断剩下节点构成的二叉排序树是否满足平衡二叉树的要求,如果不满足需要做相应的左旋右旋处理,维护成本高,因此,在工程实践上,我们更多时候使用的是红黑树这种二叉排序树,它是一种不严格的平衡二叉树,实现起来更加简单,性能也接近严格的平衡二叉树.

0

评论区