algorithm - 赤/黒の木の子供たち？

Question

この赤黒木の説明によると、木には次のプロパティが必要です。

1. ノードは赤または黒のいずれかです。
2. 根元は黒。(このルールは時々省略されます。ルートは常に赤から黒に変更できますが、必ずしもその逆であるとは限らないため、このルールは分析にほとんど影響しません。)
3. すべての葉 (NIL) は黒です。(すべての葉は根と同じ色です。)
4. すべての赤のノードの子は両方とも黒です。
5. 特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれます。

誰かがすべてのノードをブラックにするのを止めているのは何ですか?

Answer 1

可能です。しかし、条件 5 を維持するために、ノードを赤色にしたい場合があります。

例: 次の例を考えてみましょう。

  a
 / \
b   c

ここでは、すべてのノードを BLACK にすることができます

新しいノードを挿入する場合、どの色を選択しますか? 赤。黒を選ぶと条件5を満たさないからです。基本的に、条件 (1-4) のいずれかが壊れていない限り、RED ノードを挿入し続けることができます。

Answer 2

あなたが引用した最後のルールは、「特定のノードからその子孫の葉へのすべての単純なパスには、同じ数の黒いノードが含まれる」です。

すべてのノードが黒の場合、ルートからリーフへのパスには同じ数のノードが含まれている必要があります。言い換えれば、すべての葉は同じ深さです - したがって、これは完全な二分木でのみ可能です。