当前位置:首页 > 经验 >

红黑树与平衡二叉树的区别(红黑树平衡树对比)

来源:原点资讯(www.yd166.com)时间:2022-11-14 14:54:56作者:YD166手机阅读>>

因为以上插入点的特殊性,插入后的整棵树还是平衡的(插入点所在位置的节点的最高深度为5,与其它节点的最高深度相等)。

在原树上插入20:

红黑树与平衡二叉树的区别,红黑树平衡树对比(9)

可以看到,插入以后树已经不是一个平衡的二叉树(最高深度成了6),而且并不满足红黑树的要求,因为20和21均为红色,这种情况下就需要对红黑树进行变色,21需要变为黑色,22就会变成红色,如果22变成红色,则需要17和25都变成黑色:

红黑树与平衡二叉树的区别,红黑树平衡树对比(10)

而17变成黑色显然是不成立的,因为如果17变为黑色,那么13就会变为红色,不满足二叉树的规则,因此此处需要进行另一个操作---------左旋操作

红黑树与平衡二叉树的区别,红黑树平衡树对比(11)

左旋:下图就是一个左旋的例子,一般情况下,如果左子树深度过深,那么便需要进行左旋操作以保证左右子树深度差变小

红黑树与平衡二叉树的区别,红黑树平衡树对比(12)

栏目热文

红黑树二叉树的区别(红黑树和平衡二叉树区别)

红黑树二叉树的区别(红黑树和平衡二叉树区别)

很早之前就想写一篇关于红黑树的文章,但是由于担心自己理解的不透彻,就一直不敢下笔。于是在重新看了很多篇文章和资料之后,决...

2022-11-14 14:11:33查看全文 >>

红黑树的高度和深度区别(红黑树的原理动态图)

红黑树的高度和深度区别(红黑树的原理动态图)

专注于Java领域优质技术,欢迎关注作者:JasonGaoH之前在公司组内分享了红黑树的工作原理,今天把它整理下发出来,...

2022-11-14 14:34:32查看全文 >>

红黑树与b+树区别(红黑树解决什么问题)

红黑树与b+树区别(红黑树解决什么问题)

树的定义树是包含n(n>1)个结点,n-1条边的有穷集,其中:(1)每个元素称为结点;(2)有一个特定的结点称为根...

2022-11-14 14:55:20查看全文 >>

红黑树和平衡二叉树的优缺点(红黑树为什么是平衡二叉树)

红黑树和平衡二叉树的优缺点(红黑树为什么是平衡二叉树)

1 引言预防针:红黑树本来就是基本算法中的难点,所以看此文时建议先有点预备心理或知识铺垫,没接触过RBT而直接看此文的话...

2022-11-14 14:09:12查看全文 >>

红黑树为什么叫平衡二叉树(详解什么是平衡二叉树)

红黑树为什么叫平衡二叉树(详解什么是平衡二叉树)

前言面试过程中,多多少少会问一点数据结构(二叉树)的问题,今天我们来复习一下二叉树的相关问题,文末总结。1. 二叉树的由...

2022-11-14 14:52:59查看全文 >>

红黑树一定是平衡二叉树吗(红黑树是一个平衡的二叉排序树)

红黑树一定是平衡二叉树吗(红黑树是一个平衡的二叉排序树)

二叉搜索树的局限性 上一节较为详细的介绍了C语言中的二叉搜索树,提到数据采取二叉搜索树的结构存储,可以获得不错的搜索性能...

2022-11-14 14:51:45查看全文 >>

有序树和二叉树的区别(二叉判定树和二叉排序树的区别)

有序树和二叉树的区别(二叉判定树和二叉排序树的区别)

树这些基本的东西必须了解一下!数据结构之树的一些事儿树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据...

2022-11-14 14:19:14查看全文 >>

马拉松赛前一个月怎么训练计划(马拉松赛前一周怎么安排)

马拉松赛前一个月怎么训练计划(马拉松赛前一周怎么安排)

2019宜昌国际马拉松暨全国马拉松锦标赛(宜昌站),将于10月27日上午7:30在湖北宜昌市鸣枪。宜昌国际马拉松创办于2...

2022-11-14 14:25:32查看全文 >>

马拉松赛前两个月训练计划(马拉松赛前一月训练表)

马拉松赛前两个月训练计划(马拉松赛前一月训练表)

想要跑得好,科学备战不能少!撰文/柳条编辑/柳条出品/马孔多跑步研究室下个月11月,马拉松比赛将进入一个高峰期,数场上万...

2022-11-14 14:23:44查看全文 >>

马拉松赛前需要做好哪些准备工作

马拉松赛前需要做好哪些准备工作

关注慧跑,助您轻如羽、跑无伤无论是业余跑者,还是精英马拉松运动员,要想突破自己,实现PB,都必须进行一个阶段完整的周期训...

2022-11-14 14:11:01查看全文 >>

文档排行