为什么RB树的根是黑色的？

Question

如果插入新元素后，RB 树的根变为红色，则其颜色变为黑色。这是为什么？在我看来，红根也同样有效。这种颜色变化只是为了让后续操作可以更有效地完成，还是还有更多的目的？

Answer 1

一种可能的解释来自树的高度。高度在Theta(log n).

至少在 中这一点是非常清楚的Omega(log n)，因为 RB-Tree 是 BT。然后就开始O(log n)发挥作用了。

由于红色节点不能有红色父节点，因此高度不超过一个外部节点的最大黑色深度 (BD) 的两倍（所有外部节点具有相同的 BD）。因此<= log n（在地板上）。

现在想象一棵树只有一个节点 - 根。如果它是黑色的，那么我们有 1 个 BD 的所有外部节点 => 小于或等于 2 个高度，这是可以的。

但如果根是红色的，那么外部节点的深度一定小于 2 * 0，实际上它是 1。这是一个矛盾，因为1 < 0。

这就是为什么你不能总是把根从黑色变成红色。相反，您始终可以添加黑色高度，例如在删除或插入时旋转之后。