12-平衡二叉树

平衡二叉树

平衡二叉树就是对二叉查找树的优化升级,它要求每个节点的左右子树的高度相差不大于1

1.平衡二叉树的查找

平衡二叉树和二叉排序树的查找是一摸一样的。

2.平衡二叉树的顺序输出

平衡二叉树的中序遍历和二叉排序树一样,都是可以输出一个有序的数列。

3.平衡二叉树的插入

平衡二叉树在插入数据时,当发生了高度的不平衡时,会采取4种旋转操作:LL,RR,LR,RL(左左,右右,左右,右左)旋转,我们来一一分析这4种旋转方式。

RR调整

针对右孩子的右子树引起的不平衡

tree12.jpg

调整策略

  • 右孩子c左上旋转作为根节点
  • 根节点a左下旋转作为c的左子树
  • c的左子树作为a的右子树
tree8.jpg

LL调整

针对左孩子的左子树引起的不平衡

tree13.jpg

调整策略

  • 左孩子b右上旋转作为根节点
  • 根节点a右下旋转作为b的右子树
  • b的右子树作为a的左子树
tree9.jpg

LR调整

针对左孩子的右子树引起的不平衡

tree14.jpg

调整策略

  • 根节点的左孩子进行一次RR调整
  • 根节点进行一次LL调整
tree10.jpg

RL调整

针对右孩子的左子树引起的不平衡

tree15.jpg
  • 根节点的右孩子进行一次LL调整
  • 根节点进行一次RR调整
tree11.jpg

平衡调整的总结

现在我们将平衡二叉树的调整归纳成一种简单且好理解的记忆方式

  • LL失衡,我们称之为LL调整,策略是对产生失衡的节点进行两次右右旋转,第一次是对失衡节点的左孩子进行右上旋转,第二次是对失衡节点进行右下旋转。
  • RR失衡,我们称之为RR调整,策略是对产生失衡的节点进行两次左左旋转,第一次是对失衡节点的右孩子进行左上旋转,第二次是对失衡节点进行左下旋转。
  • LR失衡,我们称之为LR调整,策略是对产生失衡的节点进行左右旋转,第一次是对失衡节点的左孩子进行LL调整,第二次是对失衡节点进行RR调整。
  • RL失衡,我们称之为RL调整,策略是对产生失衡的节点进行右左旋转,第一次是对失衡节点的右孩子进行RR调整,第二次是对失衡节点进行LL调整。

注意点,LL失衡和RR失衡直接两次旋转,而LR失衡和RL失衡,是分别进行两次LL和RR的组合调整。

实战演练

现在我们有一关键字序列16,3,7,11,9,26,18,14,15,我们来逐个插入构建一棵平衡二叉树。

  1. 插入数字16,直接插入
tree31.jpg

2.插入数字3,插入后不失衡,所以不调整。

tree32.jpg

3.插入数字7,插入后如左图,发现失衡,失衡点是16,此时的失衡是LR失衡,根据总结规律,先对失衡点的左孩子进行RR调整,然后再对失衡点进行一次LL调整。

tree33.jpg

4.插入数字11,插入后,不失衡。

tree34.jpg

5.插入数字9,插入后如左图,发现失衡,此时失衡节点有两个节点16和节点7,因为代码设计是递归的判断失衡,所以从从下往上的调整,所以对失衡点16调整,此时16的失衡是LL失衡,先对失衡点16右孩子进行一次LL调整,发现竟然平衡了。所以不用继续调整了。

tree35.jpg

6.插入数字26,插入后,节点7发生了失衡,失衡是RR失衡。所以进行RR调整。

tree36.jpg

7.插入数字18,此时节点16出现了RL失衡,所以进行RL的调整策略。

tree37.jpg

8.插入数字14,此时二叉树平衡。

tree38.jpg

9.插入数字15,此时节点16发生了LR失衡,进行LR调整。

tree39.jpg

好了,上面就是一个完整的插入过程,可能你会注意到一个特殊情况,就是再插入一个节点时,平衡二叉树失衡点会不只一个,这个时候选择哪个进行调整?结合代码的思路分析,因为二叉树是递归创建的,它是由根节点往叶子节点向下递归创建的,所以检测平衡只能是逆向的,由靠近叶子的向根节点逐层调整,当发现平衡时,就不用调整了。

4.平衡二叉树的删除

平衡二叉树的删除操作分为三大部分,第一大部分是先找打这个节点,第二大部分是按照二叉排序树的删除规则进行删除(可看前面二叉排序树),第三大部分是从该删除点一直上溯到根节点逐个的判断是否失衡,根据失衡条件进行调整平衡二叉树。下面是步骤

  • 按照二叉排序树的查找规则,去找待删除的节点,没找到直接退出。
  • 根据二叉排序树总结删除规则的三条,去选择对应的删除步骤进行删除操作。
  • 从删除该节点的位置开始,一直上溯到根节点,判断是否失衡,如果失衡根据对应失衡,进行相应的调整处理。

删除演示

1.删除26,如下图所示,元素26无左右孩子,直接删除,从此处开始,上溯到根判断是否失衡,发现18节点失衡,是LL失衡,进行LL调整,后面到根都平衡,不用调整。

tree45.jpg

2.删除15,如下图所示,按照规则,15左右孩子都有,所以可以先向左走一步,再一直向右走,直到此节点无右孩子,来到了14,将14放在待删除的15位置上,如下图中间,此时从该点开始回溯到根进行调整,发现14失衡,和RL失衡,进行RL调整策略。此时发现调整完毕结束。

tree46.jpg

3.删除18,如下图所示,18只有一个左孩子16,按照删除规则,将该左孩子直接放在待删除的18位置上。此时整个二叉树上溯到根节点都是平衡的,不用调整,结束。

tree47.jpg

删除操作也讲述完毕,好累。大家多看看步骤,根据步骤去画画图就可以很好的理解了。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 最近比较忙,没闲得下时间写简书。小编在之前的分享中有讲过二叉搜索树,如下的两颗树都满足二叉搜索树的条件。 图片...
    ITsCLG阅读 941评论 0 1
  • 一、二叉查找树 1、定义:二叉查找树,也称二叉搜索树,或二叉排序树。其定义也比较简单,要么是一颗空树,要么就是具有...
    小小宁儿阅读 3,344评论 0 9
  • 参考网站 一、为什么要有平衡二叉树 二叉搜索树一定程度上可以提高搜索效率,但是当原序列有序时,例如序列 A = {...
    王王王王王景阅读 938评论 0 0
  • 教书育人很重要,但也时刻告诫自己不要忘记IT男这个身份,再忙也要抽时间学习编程知识以及总结过去积累的经验。计算机算...
    ITsCLG阅读 11,621评论 7 11
  • 一直以来,我都很少使用也避免使用到树和图,总觉得它们神秘而又复杂,但是树在一些运算和查找中也不可避免的要使用到,那...
    24K男阅读 6,784评论 5 14