当前位置:网站首页>平衡二叉树(AVL)
平衡二叉树(AVL)
2022-07-07 14:11:00 【锡兰_CC】
目录
平衡二叉树的定义
Q:什么是二叉排序树
A:二叉排序树或者是一棵空树,或者是具有如下性质的二叉树
- 1)若它的左子树不空,则 左子树 上所有结点的值 均小于 它的根结点的值
- 2)若它的右子树不空,则 右子树 上所有结点的值 均大于 它的根结点的值
- 3)左、右子树也分别是一棵二叉排序树
Q:什么是平衡二叉树
A:它或者是一颗空树,或者是具有以下性质的二叉排序树:它的左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。
定义结点左子树与右子树的高度差为该结点的平衡因子,则平衡二叉树结点的平衡因子只可能是 -1,0,1。
平衡二叉树的插入
每当在二叉排序树中插入(或删除)一个结点时,首先要检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡,则先找到路径上离插入结点最近的平衡因子的绝对值大于1的结点 A,再对以 A 为根的子树,在保持排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。
平衡二叉树的插入过程的前半部分与二叉排序树相同,但在新结点插入后,若造成查找路上的某个结点不再平衡,则需要做出相应的调整。可将调整的规律归纳为下列4种情况:
LL平衡旋转(右单旋转)
由于在结点A的左孩子(L)的左子树(L)上插入了新结点,A 的平衡因子由 1 增至 2 ,导致以 A 为根的子树失去平衡,需要一次向右的旋转操作,将 A 的左孩子 B 向右上旋转代替 A 成为根结点,将 A 结点向右下旋转成为 B 的右子树的根结点,而 B 的原右子树则作为 A 结点的左子树。
RR平衡旋转(左单旋转)
由于在结点 A 的右孩子(R)的右子树(R)上插入了新结点,A 的平衡因子由 −1 减至 −2,导致以 A 为根的子树失去平衡,需要一次向左的旋转操作。将 A 的右孩子 B 向左上旋转代替 A 成为根结点,将 A 结点向左下旋转成为 B 的左子树的根结点,而 B 的原左子树则作为 A 结点的右子树的。
LR平衡旋转(先左后右双旋转)
在 A 的左孩子(L)的右子树(R)上插入新结点,A 的平衡因子由1增至2,导致以 A 为根的子树失去平衡,需要进行两次旋转操作,先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置,然后把该 C 结点向右上旋转提升到 A 结点的位置。
RL平衡旋转(先右后左双旋转)
由于在 A 的右孩子(R)的左子树(L)上插入新结点,A 的平衡因子由 −1减至 −2,导致以 A 为根的子树失去平衡,需要进行两次旋转操作,先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置,然后把该 C 结点向左上旋转提升到 A 结点的位置。
平衡二叉树的构建
假设关键字序列为{6,1,2,5,4,3},通过该序列生成二叉排序树的过程如下:
第一步:创建一个空树
第二步:插入结点 6
第三步:插入结点 1
第四步:插入结点 2
第五步:LR旋转
第六步:插入结点 5
第七步:插入结点 4
第八步:LL旋转
第九步:插入结点 3
第十步:RL旋转
平衡二叉树的查找
在平衡二叉树上进行查找的过程与二叉排序树的相同。因此,在查找过程中,与给定值进行比较的关键字个数不超过树的深度。假设以 nh,表示深度为 h 的平衡树中含有的最少结点数。显然,nh有 n0=0,n1=1,n2=2, 并且有 nh=nh−1+nh−2+1。 可以证明,含有 n 个结点的平衡二叉树的最大深度为 O(log2n),因此平衡二叉树的平均查找长度为 O(log2n)。
边栏推荐
- 121. 买卖股票的最佳时机
- js中复选框checkbox如何判定为被选中
- 应用程序和matlab的通信方式
- What else can an ordinary person do besides working in a factory to make money?
- 星瑞格数据库入围“2021年度福建省信息技术应用创新典型解决方案”
- 航运船公司人工智能AI产品成熟化标准化规模应用,全球港航人工智能/集装箱人工智能领军者CIMC中集飞瞳,打造国际航运智能化标杆
- How does geojson data merge the boundaries of regions?
- How to determine whether the checkbox in JS is selected
- Limit of total fields [1000] in index has been exceeded
- Three. JS introductory learning notes 07: external model import -c4d to JSON file for web pages -fbx import
猜你喜欢
过度依赖补助,大客户收款难,冲刺“国产数据库第一股”的达梦后劲有多足?
Plate - forme de surveillance par étapes zabbix
AE learning 01: AE complete project summary
Three. JS introductory learning notes 15: threejs frame animation module
Sysom case analysis: where is the missing memory| Dragon lizard Technology
Unity3D_ Class fishing project, control the distance between collision walls to adapt to different models
山东老博会,2022中国智慧养老展会,智能化养老、适老科技展
喜讯!科蓝SUNDB数据库与鸿数科技隐私数据保护管理软件完成兼容性适配
Numpy --- basic learning notes
Three. JS introductory learning notes 04: external model import - no material obj model
随机推荐
The inevitable trend of the intelligent development of ankerui power grid is that microcomputer protection devices are used in power systems
航运船公司人工智能AI产品成熟化标准化规模应用,全球港航人工智能/集装箱人工智能领军者CIMC中集飞瞳,打造国际航运智能化标杆
MySQL数据库基本操作-DQL-基本查询
Bidding announcement: Fujian Rural Credit Union database audit system procurement project (re bidding)
Three. JS introductory learning notes 0: illustration of how webgl and threejs work
The unity vector rotates at a point
Logback日志框架第三方jar包 免费获取
laravel 是怎么做到运行 composer dump-autoload 不清空 classmap 映射关系的呢?
Three. JS introductory learning notes 19: how to import FBX static model
Bidding announcement: Panjin people's Hospital Panjin hospital database maintenance project
PyTorch 中的乘法:mul()、multiply()、matmul()、mm()、mv()、dot()
分步式监控平台zabbix
Talk about the cloud deployment of local projects created by SAP IRPA studio
Three. JS introductory learning notes 05: external model import -c4d into JSON file for web pages
Numpy --- basic learning notes
Multiplication in pytorch: mul (), multiply (), matmul (), mm (), MV (), dot ()
Introduction to pyGame games
SysOM 案例解析:消失的内存都去哪了 !| 龙蜥技术
Plate - forme de surveillance par étapes zabbix
Numpy -- epidemic data analysis case