为什么红黑树插入操作中新插入的节点总是红色的？

Question

想知道为什么红黑树插入时，我们先将新节点标记为红色，然后再进行一些调整？为什么不将其标记为黑色并做一些适当的调整呢？谢谢。

我认为唯一的原因是，添加红色节点不会破坏红黑树关于黑色节点相关规则的任何规则（例如从根到叶子的路径包含相同数量的黑色节点），只需要调整任何违反红色规则（即父/子不能是连续的两个红色节点），这使得代码简单。我不认为添加黑色节点并调整黑色节点数量（在不同路径上）的违规是不可能的。总之，添加黑色以外的红色节点只是为了代码简单，没有其他原因。如果我错了，请随时纠正我。

Answer 1

\n
1. 与插入黑色节点相比，插入红色节点违反红黑规则的可能性较小。这是因为，如果新的红色节点连接到黑色节点，则不会违反规则。它不会\xe2\x80\x99t创建一个\n两个红色节点在一起的情况，这会打破\n红父黑子的规则，并且\xe2\x80\x99t不会改变黑色\n高度（黑色节点的数量从根到叶）在任何路径中。
\n

2. 当然，如果将新的红色节点附加到红色节点，则会违反红父黑子的规则。然而，如果运气好的话，这种情况只会发生一半。然而，如果添加新的黑色节点，它总是会更改其路径的黑色高度，从而违反黑色高度规则。

\n

3. 此外，修复红父黑子规则的违规问题比修复黑高度规则更容易。

\n

\n\n

资料来源：Java 中的数据结构和算法第二版 - Robert Lafore第 437 页。

\n