gpt4 book ai didi

data-structures - 为什么RB树的根是黑色的?

转载 作者:行者123 更新时间:2023-12-05 07:56:43 28 4
gpt4 key购买 nike

如果在插入新元素后,RB 树的根变为红色,则其颜色变为黑色。这是为什么?在我看来,红色的根也能起到同样的作用。这种颜色变化只是简单地完成,以便可以更有效地完成后续操作,还是还有更多?

最佳答案

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

很明显至少在 Omega(log n) 中,因为 RB 树是 BT。然后是O(log n)发挥作用。

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

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

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

这就是为什么不能总是将根从黑色更改为红色的原因。相反,您始终可以添加到黑色高度,例如在删除或插入时旋转之后。

关于data-structures - 为什么RB树的根是黑色的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28267290/

28 4 0
文章推荐: html - 如何更改 Chrome 中