このバイナリツリーのバランスを取ることはできますか？

Question

私は、二分探索木のバランスをとる方法（ブルートフォース）を実装するコードを実装しようとしていた、と私は（木の）場合があることを発見し、それはバランスをとることができないようです。ツリーには、あなたは明らかにこのツリーの右側の高さは、その左側の高さよりもはるかに大きいので、私は周りの木を左に回転させる「6」、そして新しい木が

 10 
    /
    6 
     \ 
     8 
    /\ 
    7 9 

になることを見つけることができます

  6 
      \ 
      10 
     /
     8 
     /\ 
     7 9 

です

次に、ノード「10」の周りのツリーに次の段階で、私は（背中に）右回転しなければならないので、左の高さは、その右側の高さよりもはるかに大きいことになります。

このツリーのバランスを取りながら（回転、右、左、右、左...というように）そのルートノードの周りにこのツリーを回転させる無限ループが存在しなければならないようです。このツリーのバランスをとるソリューションはありますか？

Answer 1

あなたはそれがまた、アンバランスであるとして、あなたの代わりに最初の右のサブツリーを回転させる必要があり、最初の根の周りを回転するべきではありません。

はこの

 10 
    /
    8 
    /\ 
    7 9 

が回転し、

 8 
    /\ 
    7 10 
    /
    9 

に変換後、ツリーが

6 
    \ 
    8 
    /\ 
    7 10 
    /
    9 

され、その後、あなたは根の周りを回転する必要があります

8 
/\ 
    6 10 
    \ /
    7 9 

Answer 2

これを行うための最も簡単なアルゴリズムである：

1. それらのノード
2. は、元のサブツリーを取り付ける
3. 順（6、8、10、あなたの場合には）、このツリー内の3つの連続したノードを取ります順序：空、7、9、

空生じるであろう：

 8 
/ \ 
    6  10 
/\ /\ 
. 7 9 . 

この木はかなりバランスが取れています。