AVL木4回転は

Question

に動作されていない我々は、バイナリツリーのバランスを保つために、我々はRR LL RL LR foureを使用することができます知っているがアンバランスツリーはバランスをとるために作るために回転させ、しかし、我々はfllowsとしてバランスツリーを持っている場合：

 885 
     /\ 
    / \ 
    659 912 
    /\  \ 
    / \ 934 
    212 759 
/\ 
/ \ 
11 344 

我々はこのツリーにノード（168）を追加し、このようなツリー場合：

 885 
     /\ 
    / \ 
    659 912 
    /\  \ 
    / \ 934 
    212 759 
/\ 
/ \ 
11 344 
\ 
168 

ツリーがバランスされていないが、私は4つの回転（RR、LL、RLのいずれかを使用することはできません、 LR）を使用してツリーのバランスを再度調整します。誰かがなぜ私に言った？

Answer 1

ツリーは重くなっていますが、ツリーの左のサブツリーは重いままではありません。右回りにするだけです。 は、次のようにツリーが見えます右回転を行った後：

    659 
       / \ 
      / \ 
      212  885 
      /\ /\ 
      / \ / \ 
      11 344 759 912 
      \    \ 
       \    \ 
       168    934 

がやっている方法を決定するために、以下のアルゴリズムを使用してみてください：

IF tree is right heavy { 
IF tree's right subtree is left heavy { 
    Perform Double Left rotation 
} 
ELSE{ 
    Perform Single Left rotation 
} 
} 
ELSE IF tree is left heavy { 
IF tree's left subtree is right heavy { 
    Perform Double Right rotation 
} 
ELSE { 
    Perform Single Right rotation 
} 
}