紅/黑樹中的孩子？

Question

根據該explanation紅黑樹的，樹必須具有以下性質：

1. 節點是紅色或黑色。
2. 根部是黑色的。 （此規則有時省略。因爲根總是可以從紅色變成黑色，但不一定 反之亦然，這條規則對分析影響不大。）
3. 所有葉子（NIL）是黑色的。 （所有葉子與根部顏色相同）
4. 每個紅色節點的兩個孩子都是黑色的。
5. 從給定節點到其任何後代樹葉的每條簡單路徑都包含相同數量的黑色節點。

什麼是阻止別人做的每一個節點黑？

Answer 1

你報的最後一個規則是「從給定節點到任何其後代的葉子每一個簡單路徑包含相同數量的黑色結點。」

如果所有節點都黑色，然後從根到葉的任何路徑必須包含相同數量的節點。換句話說，所有的葉子都在相同的深度 - 所以這隻適用於perfect binary tree。

Answer 2

這是可能的。但爲了保持條件5，有時您可能想要爲節點RED着色。

例如，考慮下面的例子。

a 
/\ 
b c 

這裏所有的節點可以是黑色現在

如果要插入一個新的節點，你會選擇哪種顏色？紅。因爲如果你選擇黑色，條件5將不會被滿足。所以基本上你可以繼續插入RED節點，除非任何條件（1-4）沒有被破壞