在Red Black Tree Properties中不包含任何插入节点颜色的规则,无论如何我们总是插入红色节点。
如果我们插入黑色节点,它是否违反任何属性(任何规则4)?
没错!假设树中只有一个节点:
5 (black)
现在插入一个新的黑节点到树中:
5 (black)
9 (black)
现在树中所有根空路径都有相同数量的黑节点的不变量被打破了,因为从根左开始的路径有一个黑节点,从根右开始的路径各有两个。
希望这对你有帮助!
你好像在问两个问题
1)为什么在插入(title)时将节点设置为红色?
2)插入黑色是否违反任何属性?
你似乎也有一个错误的印象,认为对2)的肯定回答是对1)的自动证明。
不是这样的!将节点插入为红色也会违反RB Tree的一个属性。例如,如果您使红色节点成为另一个红色节点的子节点,您就违反了红色节点只能有黑色子节点的属性。
使其为红色的原因是,它是"更容易"修复子节点属性(通过旋转和重新绘制父/祖父母),而不是试图修复路径长度属性。也许另一个原因是,这就是作者想出来的。
也可以通过插入一个黑色节点而不重新绘制红色来修复树。也许还没有人考虑过这个问题。