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

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

AVL 트리 회전

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

오늘도 즐프하세요~

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