피벗을 중심으로 회전 할 수 없습니다.

Question

AVL 트리에 새 값을 삽입하려고합니다. 새로운 삽입은 불균형을 야기합니다 (이 기사의 내용은 Wikipedia이며 왼쪽의 경우에 속해야 함). 따라서 회전이 필요합니다. 그러나, 두 아이들이 부모보다 더 낮은되기에 결국 때문에, 현재의 상황으로 회전 할 수 없습니다 : 지금은 (11)를 삽입 할 경우

  15 
     / \ 
     10 27 
    /\  
     8 12 

, 구조 불균형된다 :

  15 
     / \ 
     10 27 
    /\  
     8 12 
     /
     11 

위의 그림과 같이 왼쪽 하위 트리가 길고 오른쪽 하위 트리가 더 길기 때문에 왼쪽 - 오른쪽 경우에 해당합니다. 그러나 요소 4에는 왼쪽과 오른쪽 하위 트리가 모두있어 회전이 가능합니다. 내가 잘못 여기서 뭐하는 거지 (12) 이하가되는 12의 두 어린이의 결과

  15 
     / \ 
     12 27 
    /\  
     10 8 
     /
     11 

: 12은 왼쪽 서브 트리를 가지고 있기 때문에 그러나 여기, 회전이처럼 보이게?

Answer 1

틀린 것으로 보입니다. 잘못된 밸런스 요소가있는 유일한 노드는 루트이므로 주위를 회전합니다.

이 경우에는 평형 인자 인 10 (루트의 왼쪽 자식)을 확인해야합니다. 즉, -1이므로 두 개의 다른 회전이 필요합니다 (왼쪽 - 오른쪽 경우). 먼저

, 우리는이 이미지의 왼쪽 상단에 따라 왼쪽으로 약 10 회전 :

그래서 우리가 얻을 : 다음

  15 
     /\ 
     12 27 
     /
     10  
    /\ 
    8 11   

당신이 다음에 계속 회전 이미지에 설명 된대로.