[자료구조] AVL 트리 회전하기 (rotation of AVL tree)

[자료구조] AVL 트리 특징 및 로테이션 기준 에서 AVL 트리의 특징 및 회전의 4가지 케이스들에 대해서 말씀드렸었는데요

로테이션을 어떻게 하는지에 대해서 좀 더 자세히 설명드리기 위해 추가 포스팅을 합니다.

AVL 트리 회전

우선 첫 번째 케이스였던 Left-Left 케이스에 대해서 살펴보도록 하겠습니다.

Left-Left 케이스는 부모노드와 pivot 노드가 모두 left heavy 인 케이스였죠. 

즉, 신규로 어떤 노드를 추가했을 때 해당 노드의 부모노드와 pivot 노드의 균형값(balance factor)이 (-)라는 얘기죠.

아래 예제를 한번 살펴보겠습니다.

 

figure1. Left-Left 에제 base tree

이런 트리가 있다고 가정해봅니다. 각 노드의 바깥쪽에 씌여진 숫자가 균형값(balance factor)입니다.

자, 이제 이 트리에 2번 노드를 추가합니다.

figure2. Left-Left 예제 신규노드 추가

새롭게 노드가 추가가 되면서 5번 노드와 10번 노드의 균형값에 변동이 생기고 10번 노드의 균형값이 -2가 되면서 AVL 트리의 조건에 위배됩니다. 따라서 회전을 해야하는데 이렇게 새로 추가한 노드의 부모 노드(5번 노드)와 pivot 노드(10번 노드)가 모두 left heavy인 경우에는 오른쪽으로 1회전을 해주면 됩니다.

figure3. Left-Left 예제 로테이션하기

오른쪽으로 회전을 해주게되면 모든 노드의 균형값이 0이 되면서 AVL 트리의 조건을 만족하게 됩니다.

 

두 번째로 왼쪽으로 회전해야하는 Right-Right 케이스를 살펴보겠습니다.

Right-Right 케이스는 부모노드와 pivot 노드가 모두 right heavy 인 케이스이죠.

아래 그림은 right-right 케이스에 대해서 왼쪽으로 회전하는 예제입니다.

figure4. AVL 트리의 왼쪽 회전 (출처: tutorialspoint.com)

최초에 A, B 노드가 있었고 C 노드가 추가가 되면서 right unbalanced 트리가 됩니다.

right-right 케이스에 해당하므로 왼쪽으로 1회전 해주면 balanced 트리가 되죠.

 

이제 세 번째 케이스인 left-right 케이스를 한번 보겠습니다.

left-right 케이스는 부모 노드와 pivot 노드의 균형값이 각각 right-heavy, left-heavy, 인 경우라고 했었습니다.

이 말은 결국 어떤 노드의 왼쪽 서브트리의 오른쪽 서브트리에 새로운 노드를 추가하게 되는 경우라고 이해하셔도 됩니다.

아래 그림을 보시면 이해가 더 빠를 겁니다.

figure5. left-right 케이스

최초에 C와 A 노드만 있었는데 B 노드가 추가가 됩니다. 그러면 A노드의 오른쪽 서브트리로 들어가게 되겠죠. 위 그림처럼 말이죠.

figure6. 왼쪽 회전

left-right 케이스라면 왼쪽으로 회전했다가 오른쪽으로 회전하면 되므로 위 그림처럼 왼쪽으로 회전을 시켜봅니다.

figure7. 왼쪽 회전의 결과

왼쪽으로 회전을 시키면 위 그림 처럼 됩니다. 어랏? 어디서 본 그림이네요?

맞습니다. 제일 처음에 봤던 left-left 케이스와 똑같아 졌습니다.

left-left 케이스면 오른쪽으로 회전을 시켜야겠죠?

figure8. 오른쪽 회전

figure9. 균형 트리

이제 균형이 모두 맞춰졌습니다.

 

마지막으로 right-left 케이스를 살펴보겠습니다.

간단하게는 left-right 케이스와 반대라고 생각하시면 됩니다. 

left-right 케이스가 왼쪽 서브트리의 오른쪽 서브트리에 새로운 노드가 추가되는 케이스였으니,

right-left 케이스는 오른쪽 서브트리의 왼쪽 서브트리에 새로운 노드가 추가되는 케이스겠죠.

그리고 그 말은 부모 노드와 pivot 노드의 균형값이 각각 left-heavy, right-heavy라는 것과 동일합니다.

그림으로 한번 살펴보겠습니다.

figure10. right-left 케이스

A, C 노드가 있었는데 B 노드가 새롭게 추가가 됩니다. C 노드의 왼쪽 서브트리로 추가가 되죠.

A노드의 오른쪽 서브트리(C가 루트노드인)의 왼쪽 서브트리에 새로운 노드가 추가가 됐습니다.

figure11. 오른쪽 회전

이런 경우 오른쪽으로 먼저 회전을 해줍니다.

figure12. 오른쪽 회전 결과

그러면?? 두 번째 케이스인 right-right 케이스가 됩니다. 그럼 왼쪽으로 회전시켜주면 되겠죠?

figure13. 왼쪽 회전

figure14. 균형 트리

자, 이렇게 마지막 네 번째 케이스도 균형 트리가 되었습니다.

 

AVL 트리의 4가지 회전 방법에 대해서 그림으로 설명을 해드렸는데요,

이해가 잘 되셨길 바랍니다.

 

이상으로 AVL 트리의 로테이션법에 대한 포스팅을 마치도록 하겠습니다.

 

오늘도 즐프하세요~

 

 

Note: left-left 케이스를 제외한 나머지 케이스들에 대한 이미지는 tutorialspoint.com 에서 가져왔습니다.