AVL 트리 네 개의 회전 작동되지

Question

우리 이진 트리의 균형을 유지하기위한, 우리는 불균형 나무가 균형을 만들기 위해 회전, 그러나 RR의 LL RL의 LR의 foure을 사용할 수 있습니다 알고 우리는 fllows로 균형 트리가있는 경우 :

을

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

우리가이 나무에 노드 (168)를 추가하고이 같은 나무가있는 경우 : LL, RR (

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

나무가 균형을하지 않습니다,하지만 난 네 회전 중 하나를 사용할 수 없습니다, 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 
} 
}