最大の高さで赤い黒の木を作成するには？

Question

赤い黒いツリーの最大高さは2log（n + 1）です。したがって、ノード数が15の場合、最大高さは2log（16）または8でなければなりません。赤い黒いツリーを描こうとしています高さは8で、ノードは15個しか使用できませんが、赤い黒い木の規則を守らなければできません。 15ノードを使用して、高さ8の赤い黒のツリーを作成するにはどうすればよいですか？

Answer 1

擬似コードから、私はCLRSから読みました。最大の高さは、ツリーに赤いノードを新規に挿入した後で、色を変更したりツリーのバランスをとるために回転が適用される前に達成されるようです。ツリーのデモを以下、この外部ノード= 3、及び最大高さ= 4：

 black(h=4) 
    /  \ 
    nul  red(h=3) 
      / \ 
      nul red (h=2) 
      / \ 
      nul  nul (h=1) 

ツリーは、次に回転なる

、得られた高さが低減さ

 black(h=3) 
    /  \ 
    red  red(h=2) 
/ \ / \ 
nul nul nul nul(h=1) 

左に回転させることによって、新たに挿入された赤のノードを修正しすべての要件を満たしています。