algorithm - 红/黑树上的 child ？

Question

根据这个explanation红黑树，树必须具有以下性质:

1. 一个节点要么是红色要么是黑色。
2. 根是黑色的。 (这条规则有时会被省略。因为根总是可以从红色变为黑色，但不一定反之亦然，此规则对分析影响不大。)
3. 所有叶子 (NIL) 都是黑色的。 (所有的叶子都和根的颜色一样。)
4. 每个红色节点的两个 child 都是黑色的。
5. 从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

是什么阻止有人让每个节点都变黑？

Answer 1

这是可能的。但是为了保持条件 5，有时您可能希望将节点着色为红色。

例如，考虑以下示例。

  a
 / \
b   c

这里所有的节点都可以是BLACK

现在如果要插入一个新节点，你会选择哪种颜色？红色的。因为如果你选择黑色，条件 5 将不满足。所以基本上你可以继续插入 RED 节点，除非任何条件 (1-4) 没有被破坏