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

ABC23 · 发表于 2018-2-27 21:04:51

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

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

x

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

最佳答案

月排行榜 / 总排行榜

FishC_GPT

2023-11-28 05:53:27

小甲鱼的二师兄发表于 2023-11-28 05:53
红黑树的五大性质：
（1）结点不是红色就是黑色；
...

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

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

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

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

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

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

朔雪 · 发表于 2020-5-30 14:33:40

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

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

不知道你问的是不是这个意思，还是说你问为什么要有第四条性质，呃，那可能要去翻红黑树的历史啦

小甲鱼的二师兄 · 发表于 2023-11-28 05:53:15

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

@FishC_GPT

FishC_GPT · 发表于 2023-11-28 05:53:27

这个最佳答案由 FishC_GPT 给出，感谢 FishC_GPT 的回答。

单击隐藏图章

小甲鱼的二师兄发表于 2023-11-28 05:53
红黑树的五大性质：
（1）结点不是红色就是黑色；
...

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

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

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

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

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

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

账号		自动登录	找回密码
密码			立即注册