algorithm - 赤黒木がX個の黒ノードとY個の赤ノードを持つことができるかどうかを見分ける方法

Question

来週、アルゴリズムの試験があり、それに備えるための質問がありました。しかし、これらの質問の1つで私は困惑しました。

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

すぐに答えられるように思えますが、気が進まないです。

CRLSは、n個の内部ノードを持つRBツリーの最大の高さを示します：2 * lg（n + 1）。

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

任意のヒント？

score 1 · Accepted Answer

これは試験の準備なので、直接答えたくはありませんが、考慮する必要があるのは、赤黒木を構築する方法を決定するプロパティです。

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

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

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

score 1 · Accepted Answer

答えは簡単です。

私たちが知っているように、赤いノードは黒い親しか持つことができません。ノードの数は、各黒ノードの両方の子が赤である場合になります。したがって、すべての黒ノードには赤の親があります。したがって、「n」の場合、黒いノード「2n」の赤いノードが可能です。

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

これがソリューションの視覚化に役立つことを願っています。

score 0 · Accepted Answer

答えは、RBツリーがリーフで黒のダミーノードを使用しているかどうかによって大きく異なります。使用している場合は、7つの黒ノードの数に含まれます。そうでない場合は、7つの黒いノードの完全なツリーを検討してください

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

10個の赤いノードを追加するのにそれほど問題はありません。

3 に答える 3