当前位置:网站首页>构建平衡二叉树「建议收藏」
构建平衡二叉树「建议收藏」
2022-08-09 23:06:00 【全栈程序员站长】
大家好,又见面了,我是你们的朋友全栈君。
我们对二叉树,二叉排序树的构建过程都很清楚,也知道二叉平衡树的概念,但是如何根据一个序列来构建平衡二叉树呢?
我们是通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式),若出现不平衡,则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。分为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的左子树)。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/105711.html原文链接:https://javaforall.cn
边栏推荐
- 《动手学深度学习》(八) -- 多尺度标检测和单发多框检测
- Force buckle: 279. Perfect square
- 【集训DAY4】异或【字典树】
- 2022-08-09 mysql/stonedb-subquery performance improvement-introduction
- 781. 森林中的兔子
- 什么是平面文件数据库? 如何导入多种格式的文件:DSV、JSON、XML?
- NTP SERVICE TASK 在GWserver配置、启用NTP服务,为当前环境提供时钟同步服务,Client主机可以从该服务器同步时间。
- 【励志】名言警句
- 关于服务治理
- Gold Warehouse Database KingbaseGIS User Manual (6.2. Management Functions)
猜你喜欢
Redis-基本介绍/linux下环境配置/配置文件
数字孪生电力系统,可视化应用实现科学调度的电子设备
FreeRTOS任务基础
网络协议05 -网络层
ES6 从入门到精通 # 15:生成器 Generator 的用法
数字孪生智慧制造生产线项目实施方案,平台认知与概念
多商户商城系统功能拆解24讲-平台端分销会员
complete knapsack theory
Gartner's global integrated system market data tracking, hyperconverged market growth rate is the first
工程 (七) ——PolarSeg点云语义分割
随机推荐
framework源码读后感
YOLOV5学习笔记(七)——训练自己数据集
ES6 从入门到精通 # 13:数组的扩展方法二
Eureka自我保护
【集训DAY3】挖金矿【二分答案】
第十五章 mysql存储过程与存储函数课后练习
ES6 Beginner to Mastery #15: Generator Usage
【集训DAY5】选数字【数学】
分布式数据库难题(二):数据复制
《GB5084-2021》PDF下载
新开窗口 展示协议
共创 Ray 中文社区,Ray Forward Meetup 2022 直播邀你参加!
【集训DAY4】矩形【线段树】
Travel with Shengteng: See all the AI attractions in Jinling City in one day
JSON对象和字符串相互转化
首席信息官如何将可持续性和技术结合起来
巴比特 | 元宇宙每日必读:国内首个数字人产业专项支持政策发布,2025年北京数字人产业规模将破500亿元...
用哈希简单封装unordered_map和unordered_set
ES6 从入门到精通 # 15:生成器 Generator 的用法
Linux安装Oracle和postgrepSQL数据库