tree - 红黑树旋转时，所有节点的黑色高度是否保留？

Question

我在考试中被问到这个问题，但是我对老师的回答不太相信，请问您对此有何看法。

红黑树上的旋转...

1. 保留所有节点的黑色高度。
2. 保留按顺序排列。

以上说法正确的是：

    A. (1) 单独
    B. (2) 单独
    C. (1) 和 (2)两者
    D. (1) 和 (2)都不是。

老师声称旋转不会保留黑色高度，答案是B：它仅保留按顺序排列。但是，我坚信它保留了所有节点的黑色高度，答案是C，而不是B。

我是对的还是我的老师是对的？

Answer 1

你的老师是对的。在Wikipedia上，我们在“插入案例 5”中找到了一个轮换示例：

左侧是一个简单的变体，右侧是一个更复杂的案例。

第二行显示旋转的结果。很明显，随着黑色根移动到右子树，左子树中的节点在其路径上失去了一个黑色节点，因此存在黑色违规。

请注意，在这样的旋转之后，通常有一种方法可以更改一个或多个节点的颜色以解决黑色违规。这就是图像底部行中所描绘的内容。但是这个动作不是轮换的一部分。

Answer 2

我同意你的教授。我不同意你关于为所有节点保留黑色高度的观点，因为旋转（以及节点重新着色是旨在恢复红黑属性的一组操作的一部分）

通常

Red-Black Tree Insertion 违反了没有连续 2 个红色节点的属性。红黑树删除违反了所有黑树从根开始的高度都相同的属性。

因此，任何修复都在树根方向上的节点上完成，并且可能有 O((log2(h /2)) 重新着色和最多 2 次旋转插入 O(log2(h)) 重新着色和最多 3删除的旋转

只有修复的最后一部分才能恢复红黑树的全部不变量集，并且任何正在进行的部分修复可能仍会使树需要进一步的修复，直到违规违规被解决。

Answer 3

这是收到的图片

非常感谢您的回复。通过查看提供的材料，更容易理解并得出结论，这不是旋转的一部分，但是，通过查看随附的图片，您不能真正说旋转时没有保留黑色高度，这就是我们有作为基础。我相信问题出在所提供的材料上，正如您所看到的，这并不清楚。但我确实明白为什么颜色的平衡不包括在旋转中。

无论如何，在插入和删除期间保持平衡条件。