赤 - 赤 - 黒の木に特定の黒い高さを持つノードの数

Question

"Red-Red-Black"の木に関する質問に宿題で尋ねられました。 （インターネットのどこかからコピーされた）赤 - 赤 - 黒ツリーを説明する：

「が赤 - 赤黒木は、以下の条件を満足する二分探索木である：

1. すべてノードは、その子の両方が
が
2. 子孫の葉へのノードからすべての単純なパスが含まれている黒で、その後、ノードは赤であり、それは親が赤なら赤または黒の
3. すべての葉が（ゼロ）は黒
4. です同じ数の黒いノード（木の黒い高さ） "

n個のノードを持つ赤赤黒のツリーを与えられたとき、黒の高さkを持つ内部ノードの最大数は何ですか？最小の数字は何ですか？

私はそれを2時間以上考えようとしていましたが、頭痛以外はどこにも行けませんでした。

ありがとうございます！

Answer 1

2つのレッドノードを連続して表示することはできません。 任意のパスを通過するときの黒ノードの数は等しくなければなりません。