8

在红黑树属性中不包含任何插入节点颜色的规则,但我们总是插入红色节点。

如果我们插入黑色节点,它是否违反任何属性(4 个规则中的任何规则)?

4

2 回答 2

10

是的!假设您的树中有一个节点:

    5 (black)

现在在树中插入一个新的黑色节点:

    5 (black)
     \
      9 (black)

现在,树中的每个 root-null 路径都有相同数量的黑色节点的不变量被打破了,因为从左根开始的路径有一个黑色节点,而从右根开始的路径各有两个。

希望这可以帮助!

于 2013-03-16T16:19:26.417 回答
4

你好像在问两个问题

1)为什么插入时(在标题中)使节点变红?

2)插入为黑色是否违反任何属性?

您似乎还误以为 2) 的“是”答案是 1) 的自动证明。

不是这样!将节点插入为红色可能违反 RB 树属性之一。例如,如果你让红色节点成为另一个红色节点的子节点,你就违反了红色节点只能有黑色子节点的属性。

将其设置为红色的原因是修复子节点属性(通过旋转和重新绘制父/祖父)“更容易”,而不是尝试修复路径长度属性。也许另一个原因是,这就是作者想出的。

也可以通过插入黑色节点而不重新绘制红色来修复树。也许还没有人考虑过。

于 2013-03-16T17:41:19.737 回答