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.

在树的底部添加一个插入，用一个带有值和 2 个黑色 nil 子节点的节点替换叶(黑色 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)