赤黒の木がxブラックノードとy赤いノードを持つことができるかどうかを判断する方法

Question

私は来週アルゴリズムで試験を受け、それを準備するための質問が与えられました。これらの質問の1つは私が困惑しています。

「7つの黒いノードと10個の赤いノードを備えた赤黒の木を描くことはできますか？なぜですか？」

すぐに答えられるように聞こえますが、私はそれを周りに心に留めることはできません。

CRLSは、N内部ノードを備えたRBツリーの最大高さを与えてくれます：2*LG（N+1）。

この補題だけで問題を解決できると思いますが、確かではありません。

任意のヒント？

Answer 1

これは試験の準備であるため、私はあなたに直接の答えを与えたくありませんが、あなたが考慮する必要があるのは、あなたが赤黒の木を構築する方法を支配する特性だと思います：

1. ノードは赤または黒です。
2. ルートは黒です。 （このルールは他の定義から省略されることがあります。ルートは常に赤から黒に変更される可能性があるため、必ずしもその逆ではないため、このルールは分析にほとんど影響しません。）
3. すべての葉は黒です。
4. すべての赤いノードの両方の子供は黒です。
5. 特定のノードからその子孫のいずれかまでのすべての単純なパスには、同じ数の黒いノードが含まれています。

（ウィキペディアページからこれらを盗んだ： http://en.wikipedia.org/wiki/red-black_tree)

リストしたノードの数を考えると、これらすべてのプロパティを満たすことができますか？

Answer 2

答えは簡単です。

赤いノードには黒い親を持つことができることがわかっているように。ノードは、各黒いノードの両方の子供が赤である場合、したがって、すべての黒いノードが赤い親を持っている場合です。したがって、 'n'ブラックノード 'の場合は2n'赤ノードが可能です。

このように考えてください：

1. 最初のノード（ルート）を入れて黒くする
2. 両方の子供を赤くします
3. これらの両方の赤いノードの左と右の子供を黒くし、これらすべての黒いノードのために、
4. ブラックノードカウントが指定された値に達するまで、ルートで後に続くのと同じ手順に従ってください（この場合7）

これがあなたが解決策を視覚化するのに役立つことを願っています。

Answer 3

答えは、RBツリーが葉で黒いダミーノードを使用しているかどうかに大きく依存し、もしそうなら、それらは7つの黒いノードのカウントに含まれています。そうでない場合は、7つの黒いノードの完全なツリーを検討してください

        *
       / \
      *   *
     /\   /\
    *  * *  *

10個の赤いノードの追加に問題はありません。