algorithm - 将节点插入红黑树时，如果叔叔是黑人，父母是黑人怎么办？

Question

我知道在插入新节点时，有两种情况，叔叔在红黑树中是黑色的。但在所有情况下，父母都是红色的。如果父母是黑人，则没有违规。在这种情况下，我该怎么办？

Answer 1

如果您最终将一个节点添加到红/黑树中并且其父节点是黑色的，您可以将节点设置为红色并结束。没有必要进行任何修复。如果您查看红/黑树的规则，这不会导致任何新的违规，因为所有根空路径仍然通过相同数量的黑色节点。

不同的观点：如果您将红/黑树视为等距树或 2-3-4 树，则此规则对应于取一个带有一个键的叶子并添加另一个键，这不需要任何进一步的修正脚步。