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

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个黑节点。如果你试图插入一个新的节点16 <15作为黑节点(记住你在添加的节点下添加了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)