红黑树 - 黑高度限制

Question

我正在阅读有关红黑树的维基百科。

有人能详细解释第五个限制吗：

1. 节点要么是红色，要么是黑色。
2. 根是黑色的。
3. 所有叶子（NIL）都是黑色的。（所有叶子的颜色与根相同。）
4. 每个红色节点的两个子节点都是黑色的。
5. 从给定节点到任何后代叶子的每条简单路径都包含相同数量的黑色节点。

我很难理解它，因为在插入的最终情况之后（维基上的第5种情况），示例RBT的状态如下：

4和5难道不比1、2、3多一个黑节点吗？

- bunnybare

---

不行，因为1、2和3是黑节点，而4和5不是，所以这五条路径中都有两个黑节点。 - Ian McMahon

肯定是这样的，不是吗？现在你让我想知道维基百科也许是错的。难道维基百科会有错吗？这动摇了我的世界观！ - Ian McMahon

是的，维基百科是错误的，U 应该从一开始就是红色的。因此最后也应该是红色的。 - Roee Gavirel

维基百科文章中的图片在第5条属性和着色方面是误导性的。 - Alexey Frunze

是的，实际上，忽略颜色，在旋转之前和之后，“tree”的结构完全相同，只是镜像而已，因此旋转没有任何意义... - Roee Gavirel

Answer 1

1、2、3、4和5都是子树。我们知道树1、2和3的根节点颜色为黑色。我们不知道节点1-5中是否有叶节点，因为插入操作可能在新插入节点的祖父节点N上递归调用（来自插入情况3）。

旋转前后，子树1、2和3都位于一个黑节点下方（旋转前为G，旋转后为P），而子树4和5都位于两个黑节点下方（旋转前为G和U，旋转后为P和U）。子树1、2和3每个比子树4和5多一个黑节点。

- James

---

深入研究后，我会选择这个方案。1、2、3、4和5本质上不是叶子节点，而是它们自己的子树。N和G有黑色子节点（1、2、3的头），因此从那里出发的每条路径实际上并没有改变，因为它向上的黑色节点数量与之前相同。在旋转之前，通过U的每条路径都有U和G作为黑色节点（两个），因此旋转后，每条路径现在必须通过U和P作为黑色节点（两个）。这与之前的黑色节点数相同。因此，在假设下面的子树限制保持不变的情况下，该限制仍然成立。 - bunnybare

此外，子树1、2和3比4和5多一个黑节点，因为4和5通过U来获取它们需要匹配1、2和3的额外黑节点。我现在有点明白了。 - bunnybare

Answer 2

我刚刚仔细阅读了它，似乎图片出了问题。

由于N是刚插入的节点，这意味着在P下最后一个insert之前有子节点[1,3]或[2,3]（分别插入2或1）。因此，在最后一次插入之前，在P和U之前必须是红色的（而4、5为黑色）。

- Roee Gavirel

---

不，这个图表有双重作用。它适用于两种情况： （i）N是刚插入的节点，在这种情况下1和2不存在 （ii）插入的节点在子树1或2中远下方，N是原始节点的祖父或曾祖父等，现在需要修复的新节点。对于（ii）的情况，只要当前父节点和当前叔叔都是红色的，并且祖父的父节点也是红色的，就会循环向根部前进。 - SJHowe

Answer 3

恭喜詹姆斯解密了维基图表！它没有错，只是含糊不清。

该页面的“讨论”标签提到，“三角形并不代表叶子而是子树。某些子树顶部有黑色圆圈，表示它们的根必须是黑色。”

显然，缺少圆圈的三角形代表的是根节点颜色和树深度未知（且可能无关）的子树（包括叶子）。

因此，这些图表并不能提供足够的信息来判断是否违反了“规则5”。我们必须认为它没有违反规则。

- Chris Pearson

Answer 4

NIL节点配置完全是可选的。它们之所以是黑色的唯一原因是您想默认保存额外的红色节点。它们可以随后根据需要变为红色。

分配的黑色节点增加了黑高度，这也是一个可选的高度差异。因为您必须在某个地方记录NIL标志，所以可以将其分配为黑色节点。

您只能节省1位地址空间；通常系统非常接近其极限。

- cheeseandtomato