红黑树插入:为什么插入时使节点变为红色



在Red Black Tree Properties中不包含任何插入节点颜色的规则,无论如何我们总是插入红色节点。

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

没错!假设树中只有一个节点:

    5 (black)

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

    5 (black)
     
      9 (black)

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

希望这对你有帮助!

你好像在问两个问题

1)为什么在插入(title)时将节点设置为红色?

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

你似乎也有一个错误的印象,认为对2)的肯定回答是对1)的自动证明。

不是这样的!将节点插入为红色也会违反RB Tree的一个属性。例如,如果您使红色节点成为另一个红色节点的子节点,您就违反了红色节点只能有黑色子节点的属性。

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

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

最新更新