AVL 회전 - 회전시킬 노드

Question

AVL 트리에 대한 많은 소스를 읽었지만이 문제를 해결 한 사람을 찾지 못했습니다. AVL 트리가 불균형 해지면 어떤 노드를 먼저 회전해야합니까? 루트와 자식 (25) 양이 불균형 될 것

10 
/\ 
    5 25 
    /
     20 

내가 15을 추가하려고 해요 :

가정 나는 나무가있다.

10 
/\ 
    5 25 
    /
     20 
    /
    15 

나는 다음과 같은 트리의 결과, 25의 RR 회전 (또는 단일 회전) 할 수

다음 트리를 만들어

 10 
    /\ 
    5 20 
     /\ 
     15 25 

또는 루트에 대한 RL 회전 (더블 회전) :

20 
/\ 
    10 25 
/\  
5 15 

여기서 어떤 회전이 가장 적합한 지 혼란 스럽습니다.

Answer 1

여기서 RR 회전이 정확합니다. 회전은 규칙이 깨지 자마자 (낮게) 이루어져야합니다. 여기는 25 명입니다.

높은 회전 수는 먼저 규칙을 어기는 것이 아니며 두 번째로는 첫 번째 시야에서 그렇게 보이지는 않지만 너무 복잡해집니다.