data-structures - 为什么我们不在红黑树插入中添加一个黑色节点而不是一个红色节点？

Question

在红黑树插入中，我们总是选择将新节点添加为红色，这样我们就可以避免改变树的黑色高度。为什么这比添加黑色节点更可取？

Answer 1

我认为这是由于红黑树的规则......

1. A node is either red or black.
2. The root is black.
3. All leaves (NIL) are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

在树的底部添加了一个插入，将一个叶子（黑色 nil）节点替换为一个具有值和 2 个黑色 nil 子节点的节点。规则 5 规定每条路径上的黑色节点数必须相同。如果您添加了一个黑色节点，您将违反此规则。我将尝试说明。

                       B(10)
             R(5)                    B(15) 
    B(1)              B(6)       B(NIL)   B(NIL)
B(NIL) B(NIL)    B(NIL) B(NIL)

您会注意到，在每条路径上都有 3 个黑色节点。如果您尝试在 15 下插入一个新节点 16 作为黑色节点（请记住，您正在添加的节点下添加 2 个黑色 nil 节点），该路径将变得更长 (4)。像这样是不正确的：

                       B(10)
             R(5)                     B(15) 
    B(1)              B(6)       B(NIL)     B(16)
B(NIL) B(NIL)    B(NIL) B(NIL)          B(NIL) B(NIL)

为了满足所有规则，您需要插入一个红色节点，并且每条路径上的黑色节点数将保持相等。

                       B(10)
             R(5)                     B(15) 
    B(1)              B(6)       B(NIL)     R(16)
B(NIL) B(NIL)    B(NIL) B(NIL)          B(NIL) B(NIL)