构建平衡二叉树「建议收藏」

构建平衡二叉树「建议收藏」构建平衡二叉树

大家好,又见面了,我是你们的朋友全栈君。

    我们对二叉树,二叉排序树的构建过程都很清楚,也知道二叉平衡树的概念,但是如何根据一个序列来构建平衡二叉树呢?

    我们是通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式),若出现不平衡,则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。分为LL型、RR型、LR型和RL型4种类型,各调整方法如下(下面用A表示最低不平衡结点):

(1)LL型调整:

    由于在A的左孩子(L)的左子树(L)上插入新结点,使原来平衡二叉树变得不平衡,此时A的平衡因子由1增至2。下面图1是LL型的最简单形式。显然,按照大小关系,结点B应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡,A结点就好像是绕结点B顺时针旋转一样。

构建平衡二叉树「建议收藏」

    LL型调整的一般形式如下图所示,表示在A的左孩子B的左子树BL(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下:①将A的左孩子B提升为新的根结点;②将原来的根结点A降为B的右孩子;③各子树按大小关系连接(BL和AR不变,BR调整为A的左子树)。

构建平衡二叉树「建议收藏」

(2)RR型调整:

    由于在A的右孩子(R)的右子树(R)上插入新结点,使原来平衡二叉树变得不平衡,此时A的平衡因子由-1变为-2。图3是RR型的最简单形式。显然,按照大小关系,结点B应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡,A结点就好像是绕结点B逆时针旋转一样。

构建平衡二叉树「建议收藏」

    RR型调整的一般形式如下图4所示,表示在A的右孩子B的右子树BR(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下:①将A的右孩子B提升为新的根结点;②将原来的根结点A降为B的左孩子;③各子树按大小关系连接(AL和BR不变,
BL
调整为A的右子树)。

构建平衡二叉树「建议收藏」

(3)LR型调整:

    由于在A的左孩子(L)的右子树(R)上插入新结点,使原来平衡二叉树变得不平衡,此时A的平衡因子由1变为2。图5是LR型的最简单形式。显然,按照大小关系,结点C应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡。

构建平衡二叉树「建议收藏」

    LR型调整的一般形式如下图6所示,表示在A的左孩子B的右子树(根结点为C,不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下:①将C的右孩子B提升为新的根结点;②将原来的根结点A降为C的右孩子;③各子树按大小关系连接(BL和AR不变,CL和CR分别调整为B的右子树和A的左子树)。

构建平衡二叉树「建议收藏」

(4)RL型调整:

    由于在A的右孩子(R)的左子树(L)上插入新结点,使原来平衡二叉树变得不平衡,此时A的平衡因子由-1变为-2。图7是RL型的最简单形式。显然,按照大小关系,结点C应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡。

构建平衡二叉树「建议收藏」

    RL型调整的一般形式如下图8所示,表示在A的右孩子B的左子树(根结点为C,不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下:①将C的右孩子B提升为新的根结点;②将原来的根结点A降为C的左孩子;③各子树按大小关系连接(AL和BR不变,C
L和CR分别
调整为A的右子树和B的左子树)。

构建平衡二叉树「建议收藏」


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/105711.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • leetcode 回文数_字符串反转java

    leetcode 回文数_字符串反转java原题链接请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。函数 myAtoi(string s) 的算法如下:读入字符串并丢弃无用的前导空格检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。将前面步骤读入的这些数字转换为整数(即,“1

  • hdu 1203 I NEED A OFFER!

    hdu 1203 I NEED A OFFER!

  • Python图像处理之小波去噪

    Python图像处理之小波去噪在此前的文章中,我们讨论了在Python中利用pywt包提供的API对图像做小波分解的基本方法。小波变换在图像处理中的一个具体应用就是平滑去噪。后续我们还会从原理上讨论如何利用小波变换来设计图像去噪算法。但在此之前,本文将主要演示,利用Python中已有的API进行图像小波去噪的方法及效果

  • ipset详解[通俗易懂]

    ipset详解[通俗易懂]ipset创建:create创建一个新的ipset集合:ipsetcreateSETNAMETYPENAMESETNAME是创建的ipset的名称,TYPENAME是ipset的类型:TYPENAME:=method:datatype[,datatype[,datatype]]method指定ipset中的entry存放的方式,随后的datatype约定了每个entry…

  • 小草1.3.0

    小草1.3.0VERSION转载于:https://www.cnblogs.com/llw87/p/10149903.html

  • navicat15免费激活码_最新在线免费激活2022.01.26

    (navicat15免费激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号