当前位置:首页 > 经验 >

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

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

当我们插入值为66的节点的时候,示意图如下:

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

很明显,这个时候结构依然遵循着上述5大特性,无需启动自动平衡机制调整节点平衡状态。

如果再向里面插入值为51的节点呢,这个时候红黑树变成了这样。

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

这样的结构实际上是不满足性质4的,红色两个子节点必须是黑色的,而这里49这个红色节点现在有个51的红色节点与其相连。

这个时候我们需要调整这个树的结构来保证红黑树的平衡。

首先尝试将49这个节点设置为黑色,如下示意图。

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

这个时候我们发现黑高是不对的,其中 60-56-45-49-51-null 这条路径有 4 个黑节点,其他路径的黑色节点是 3 个。

接着调整红黑树,我们再次尝试把45这个节点设置为红色的,如下图所示:

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

栏目热文

红黑树与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查看全文 >>

二叉树和红黑树(二叉树和树的关系)

二叉树和红黑树(二叉树和树的关系)

红黑树在工程中的使用,红黑树是平衡树的一种。1. 红黑树顺序的功能2. 快速查找的功能1.二叉树插入1. 如果比当前根节...

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

为什么用红黑树而不是二叉树(红黑树和二叉树优缺点)

为什么用红黑树而不是二叉树(红黑树和二叉树优缺点)

上两节,我们依次讲了树、二叉树、二叉查找树。二叉查找树是最常用的一种二叉树,它支持快速插入、删除、查找操作,各个操作的时...

2022-11-14 14:26:38查看全文 >>

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

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

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

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

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

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

红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。简单说就是可用于二分查找的(二叉查找树),且高度是平衡的(...

2022-11-14 14:54:56查看全文 >>

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

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

二叉搜索树的局限性 上一节较为详细的介绍了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查看全文 >>

文档排行