algorithm - 红黑树插入：为什么插入时节点会变成红色？

Question

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

如果我们插入黑色节点，它是否违反任何属性（4 个规则中的任何规则）？

Answer 1

是的！假设您的树中有一个节点：

    5 (black)

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

    5 (black)
     \
      9 (black)

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

希望这可以帮助！

Answer 2

你好像在问两个问题

1）为什么插入时（在标题中）使节点变红？

2）插入为黑色是否违反任何属性？

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

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

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

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