在红黑树旋转中，是否保留了所有节点的黑色高度？

Question

我是在一次考试中被问到这个问题的，但我并不完全相信老师的回答，我想问你对此有何看法。

红黑树上的旋转.

1. 保留所有节点的黑色高度。
2. 保持有序订购。

上面的陈述是正确的：

A. (1)

B. (2)

C. (1)和(2)

D.非(1)或(2)。

老师声称旋转并不能保持黑色的高度，答案是B：它只保留顺序排序。然而，我坚信它保留了所有节点的黑色高度，答案是C，而不是B。

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

Answer 1

你的老师是对的。在维基百科上，我们在“插入案例5”中找到了一个旋转的例子：

​

​

左边是一个简单的变体，右边是一个更精细的情况。

第二行显示旋转的结果。很明显，当黑根移动到右边的子树时，左侧子树中的节点在其路径上丢失了一个黑色节点，因此出现了黑冲突。

注意，在这样的旋转之后，通常会有一种方法来改变一个或多个节点的颜色来解决黑冲突。这是在图像的底部行的图片。但是这个动作不是旋转的一部分。

Answer 2

我同意你教授的意见。我不同意您关于所有节点保留黑色高度的意见，因为轮转(以及节点回收是旨在恢复红黑属性的一组操作的一部分)。

通常

红黑树插入违反了连续两个红色节点的属性.红黑树的删除违反了所有黑树的属性，所有的根树的高度都是一样的。

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

只有修复的最后一部分，才能恢复红黑树的全部不变量集，任何中途的局部修复都可能会让树需要进一步的修正，直到违规行为得到解决为止。

Answer 3

这是收到的图像

非常感谢你的答复。通过观察这些材料，可以更容易地理解并得出结论，这不是旋转的一部分，但是，通过查看附图，你不能说黑色的高度在旋转时没有被保留，这就是我们作为基础的。我认为问题在于所提供的材料，正如你所看到的，这一点并不清楚。但是我明白为什么颜色的平衡不包括在旋转中。

无论如何，在插入和删除过程中都会保持平衡状态。