私の宿題からの質問の 1 つは、の正確な下限を見つけることでした。
(#black nodes)/(#red nodes)
rb ツリーで。境界は漸近的であってはなりません。助言がありますか？
どうぞよろしくお願いいたします。
1 に答える
3
これが宿題だと仮定すると：
ウィキペディアから RedBlack Trees のいくつかのプロパティを確認してみましょう。
- ...
- 根元は黒。
- 葉はすべて黒い。
- すべての赤のノードの子は両方とも黒です。
- ...
#B/#R の下限を取得するには、できるだけ多くの赤いノードを持つツリーを構築します。(残念ながら、2,3,4 のため、真っ赤なツリーを構築することはできません)
検討する価値のあるいくつかの質問:
- バランスの取れたツリーまたはあまりバランスの取れていないツリーに、より多くの赤いノードを適合させることができますか?
- 偶数または奇数の最大高さは違いますか?
- ツリーに 3、7、...、(2^n)-1 のバック ノードが含まれている場合、赤いノードはいくつ収まりますか?
于 2011-04-12T06:51:05.483 に答える