AVL 트리 잔액

Question

AVL 트리를 구현했지만 문제가 있습니다.

한다고 가정 나는 다음과 같은 한 나무 :

가 지금은 왼쪽에 Node5를 회전해야합니다 :

그리고 다른 노드를 추가 한 후

그러나 회전 후에도 여전히 불균형합니다.

어디에서 실수합니까?

Answer 1

제시된 시나리오는 오른쪽 - 왼쪽의 경우 this 설명에서와 일치합니다.

실수로 하위 트리의 회전을 먼저 수행하지 않고 불균형 노드 (5)를 한 번에 회전하는 것은 실수입니다.

balance(N) = Depth(Nleft) - Depth(Nright) 

if (balance(P) > 1) // P is node 5 in this scenario 
{ 
    if (balance(L) < 0) 
    { 
     rotate_left(L); 
    } 

    rotate_right(P); 
} 
else if (balance(P) < -1) // P is node 5 in this scenario 
{ 
    if (balance(R) > 0) // R is node 11 in this scenario 
    { 
     rotate_right(R); // This case conforms to this scenario 
    } 

    rotate_left(P);  // ... and of course this, after the above 
} 

그래서 때로는 두 개의 회전이 필요합니다 오른쪽 서브 트리로의 왼쪽 서브 트리로 불균형 노드로 P, L 및 R을 가진 일반적으로

다음과 같은 규칙을 삽입에 따라야한다 수행 할, 그리고 때로는 오직 하나.

이 멋지게 Wikipedia에서 가시화 : 두 개의 회전이 필요할 때

상단 행 상황을 보여줍니다. 가운데 행은 한 회전으로 충분할 때 가능한 시나리오를 나타냅니다. 추가 회전은 최상위 행 시나리오를 중간 행 시나리오로 변환합니다. 이 트리 특히

는 : 7 후

첨가된다

는

5의 균형 2이다. 위 코드는 Wikipedia 그림에서 위의 주석으로 표시된 시나리오와 맨 위의 시나리오 (오른쪽의 시나리오)에 부합합니다.그래서 5 전에 마우스 오른쪽 버튼으로 회전 할 필요가 11 오른쪽 서브 트리, 왼쪽 회전 :

그리고 그것은된다 :

을 만 지금은 단순한 사건 (위키 피 디아 그림에서 가운데 ​​행 오른쪽 시나리오) 5에서 왼쪽으로 한 바퀴 씩 균형을 복원하려면

그리고 나무는 다시 균형된다 :

Answer 2

날 AVL 트리, 어떤 가장 왼쪽의 잎에서 각 노드의 높이 차이로 이진 트리를 들어, 더 포괄적으로 을 분석 해보자 가장 오른쪽에있는 잎은 {-1, 0, 1} 내에 있어야합니다. AVL에 대한

삽입 :

AVL insertion- L 네 가지 경우가 있습니다

- L L - R R - R R - L

지금, 경우 (A). [균형> 1 인 경우] LL (왼쪽 - 왼쪽) 노드 X가 {-1, 0, 1} 제약 조건을 위반하고 이 오른쪽보다 높이를 남겼습니다. L의 첫 번째 왼쪽에 의 왼쪽 하위 하위 Y 다시 오른쪽보다 큽니다. L 동작 - Y를 시계 방향으로 돌립니다. 즉. 오른쪽 회전.

case (b) (L -R case) Z 노드가 삽입 될 것이라고 가정하면 Z가 먼저 평가되고, 왼쪽 또는 오른쪽에 배치됩니다. 맞아, 더 많은 체중이 있다면, 왼쪽으로 가볍게. Z ', new node, wt (Z')> wt (Z), 즉 Z '가 Z의 오른쪽 자식으로 삽입되면, 링크 ZZ'는 시계 반대 방향으로 회전합니다. 위의 경우 (a)를 사용하여 LL 경우이므로 해결됩니다. 즉. 왼쪽으로 한 번 회전 한 후 오른쪽으로 한 번 회전.

사례 (c) [균형이 맞으면 <-1] (R-R 경우) 마찬가지로 R-R 경우 조정을 위해 이진 검색 규칙을 적용하기 만하면이 사례가 작동합니다. 즉. 왼쪽 회전.

case (d) (R-L 경우) 먼저 R-R 경우로 변환되므로 위의 경우 (c)를 사용하여 해결됩니다. 즉. 오른쪽에서 한 번, 왼쪽에서 한 번 회전.