鱼C论坛

 找回密码
 立即注册
查看: 3152|回复: 3

[已解决]红黑树!!!!!!

[复制链接]
发表于 2018-2-27 21:04:51 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
红黑树的五大性质:
(1)结点不是红色就是黑色;
(2)树根结点是黑色;
(3)叶子结点是黑色;
(4)每个红色结点的孩子都是黑色的(反之不一定成立)
(5)从任一结点到每个叶子结点的所有路径包含相同数目的黑色结点
===============================================
我的问题——哎,还是直接举个例子好了。
(红黑树新结点插入)我们知道新插入的结点必须是红色的(规定),现在假设插入位置的父结点、插入位置的叔叔结点都是红色的
这违背了红黑树的性质4,操作如下:1)把父亲变成黑色,2)把叔叔变成黑色,3)把祖父结点变成红色,4)把祖父结点作为新的当前结点,递归操作
===============================================
我的问题是,你看这里为什么要『刻意的把祖父结点和它的两个孩子搞成符合性质4的,即每个红色结点的两个孩子都是黑色』——如果不这样,保持祖父结点还是黑色,不就不会涉及性质4了么,这样不也省事么—,,为什么实际操作中『不保持祖父为黑色,而刻意的把它变成红色』???
最佳答案
2023-11-28 05:53:27
小甲鱼的二师兄 发表于 2023-11-28 05:53
红黑树的五大性质:
(1)结点不是红色就是黑色;
...

这个操作的目的是为了保持红黑树的性质5,即从任一结点到每个叶子结点的所有路径包含相同数目的黑色结点。

当插入位置的父结点和叔叔结点都是红色时,我们不能直接改变它们的颜色,并把祖父结点变为黑色,因为这样会导致性质5被破坏。

通过将祖父结点变为红色并将父节点和叔叔结点变为黑色,我们可以保持性质5。这是因为如果插入位置的父结点和叔叔结点都是红色,那么它们的子树中必然有更多的黑色结点。将父结点和叔叔结点变为黑色后,祖父结点向上增加一个红色结点,同时减少一个黑色结点,因此仍然保持了性质5。

这个操作还有一个好处是,它能够简化后续的平衡调整过程。在向上递归调整中,我们只需要关心当前结点和它的父结点是否需要进行旋转操作,而不用考虑祖父结点的情况。如果保持祖父结点为黑色,我们会增加额外的判断条件和旋转操作,使得代码变得复杂。

总的来说,通过将祖父结点变为红色,我们可以保持性质5,并简化平衡调整过程。同时,这个操作也符合了红黑树的设计原则,即通过一系列的调整操作,使得树的结构尽可能平衡。

以上回复来自 -- ChatGPT(FishC官方接口),如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-5-30 14:33:40 | 显示全部楼层
还是没太看明白你在问什么,但是你一开始给的红黑树的性质的表述就让人很迷糊,你可以这样理解:
红黑树的五大性质:
(1)每个节点不是红色就是黑色
(2)树的根节点必须是黑色
(3)我们认为红黑树的终端节点是黑色,(但实际上终端节点是NULL,我们认为他是黑色)也称为“黑哨兵”,用NIL表示终端节点
(4)树中不允许两个红节点互为父子关系
(5)从树中任一节点出发,到其所有可能到达的终端节点的各条路径上,黑节点的数目必须完全相同

然后你的问题,插入节点的父亲和叔叔都是红色,爷爷是黑色的情况,我们知道新插入的节点一定是红色,这样的话就跟父亲违反了性质4,就需要调整,我们肯定不能改变新插入的节点的颜色(不然干嘛不直接添加黑色的节点呢?),所以我们就要改变父亲和叔叔的颜色,把他们变成黑色,就好了,这样的话就不会违反第四条性质了,但是其他路径并没有调整啊,这条路径平白无故增加几个黑节点就会又违反第五条性质,那么这时候为了保持第五条性质,就把爷爷变红,那爷爷变红之后会不会爷爷和爷爷的爸爸又会违反第四条性质呢?这是有可能的,所以又以爷爷为讨论对象,进行同样的讨论和操作。
什么时候会结束?那就看什么时候不违反红黑树五条性质了就结束呗,可能会被翻到根去哈哈

不知道你问的是不是这个意思,还是说你问为什么要有第四条性质,呃,那可能要去翻红黑树的历史啦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-11-28 05:53:15 | 显示全部楼层
红黑树的五大性质:
(1)结点不是红色就是黑色;
(2)树根结点是黑色;
(3)叶子结点是黑色;
(4)每个红色结点的孩子都是黑色的(反之不一定成立)
(5)从任一结点到每个叶子结点的所有路径包含相同数目的黑色结点
===============================================
我的问题——哎,还是直接举个例子好了。
(红黑树新结点插入)我们知道新插入的结点必须是红色的(规定),现在假设插入位置的父结点、插入位置的叔叔结点都是红色的
这违背了红黑树的性质4,操作如下:1)把父亲变成黑色,2)把叔叔变成黑色,3)把祖父结点变成红色,4)把祖父结点作为新的当前结点,递归操作
===============================================
我的问题是,你看这里为什么要『刻意的把祖父结点和它的两个孩子搞成符合性质4的,即每个红色结点的两个孩子都是黑色』——如果不这样,保持祖父结点还是黑色,不就不会涉及性质4了么,这样不也省事么—,,为什么实际操作中『不保持祖父为黑色,而刻意的把它变成红色』???

@FishC_GPT
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-11-28 05:53:27 | 显示全部楼层    本楼为最佳答案   
小甲鱼的二师兄 发表于 2023-11-28 05:53
红黑树的五大性质:
(1)结点不是红色就是黑色;
...

这个操作的目的是为了保持红黑树的性质5,即从任一结点到每个叶子结点的所有路径包含相同数目的黑色结点。

当插入位置的父结点和叔叔结点都是红色时,我们不能直接改变它们的颜色,并把祖父结点变为黑色,因为这样会导致性质5被破坏。

通过将祖父结点变为红色并将父节点和叔叔结点变为黑色,我们可以保持性质5。这是因为如果插入位置的父结点和叔叔结点都是红色,那么它们的子树中必然有更多的黑色结点。将父结点和叔叔结点变为黑色后,祖父结点向上增加一个红色结点,同时减少一个黑色结点,因此仍然保持了性质5。

这个操作还有一个好处是,它能够简化后续的平衡调整过程。在向上递归调整中,我们只需要关心当前结点和它的父结点是否需要进行旋转操作,而不用考虑祖父结点的情况。如果保持祖父结点为黑色,我们会增加额外的判断条件和旋转操作,使得代码变得复杂。

总的来说,通过将祖父结点变为红色,我们可以保持性质5,并简化平衡调整过程。同时,这个操作也符合了红黑树的设计原则,即通过一系列的调整操作,使得树的结构尽可能平衡。

以上回复来自 -- ChatGPT(FishC官方接口),如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 07:50

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表