algorithm - 红/黑树上的孩子？

Question

根据红黑树的这种解释，树必须具有以下性质：

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

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

Answer 1

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

例如，考虑以下示例。

  a
 / \
b   c

这里所有节点都可以是黑色的

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

Answer 2

您引用的最后一条规则是“从给定节点到其任何后代叶子的每个简单路径都包含相同数量的黑色节点。”

如果所有节点都是黑色的，那么从根到任何叶子的路径必须包含相同数量的节点。换句话说，所有的叶子都处于相同的深度——所以这仅适用于完美的二叉树。