자바스크립트로 배우는 AVL 트리의 4가지 회전 방법

AVL 트리는 스스로의 균형을 유지하기 위해 다음과 같은 네 가지 종류의 회전(rotation)을 수행할 수 있습니다.

• 좌회전(Left Rotation)
• 우회전(Right Rotation)
• 좌-우 회전(Left-Right Rotation)
• 우-좌 회전(Right-Left Rotation)

앞의 두 가지는 단일 회전(single rotation)이고, 나머지 두 가지는 단일 회전을 조합한 이중 회전(double rotation)입니다. 트리가 불균형 상태가 되려면 최소한 높이가 2인 트리가 필요하므로, 이 간단한 트리를 예로 들어 각 회전 방법을 하나씩 살펴보겠습니다.

좌회전 (LL 회전)

노드가 오른쪽 서브트리의 오른쪽 서브트리에 삽입되어 트리의 균형이 깨진 경우에는 단일 좌회전을 수행합니다.

위 예시에서 노드 A는 A의 오른쪽 서브트리에 새 노드가 삽입되면서 불균형 노드가 되었습니다. 이때 B를 새 루트로 만들고 A를 B의 왼쪽 서브트리로 내리는 좌회전을 수행하면 균형이 복원됩니다. 왼쪽-왼쪽(Left-Left) 상황에서 발생하는 회전이라 하여 LL 회전이라고도 부릅니다. 자바스크립트로 구현하면 다음과 같습니다.

function rotationLL(node) {
let tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}

우회전 (RR 회전)

반대로 노드가 왼쪽 서브트리의 왼쪽 서브트리에 삽입되면 AVL 트리의 균형이 깨질 수 있으며, 이때는 우회전(right rotation)이 필요합니다.

그림에서 보듯이 우회전을 수행하면 불균형 노드가 자신의 왼쪽 자식의 오른쪽 자식 위치로 내려갑니다. 오른쪽-오른쪽(Right-Right) 상황에서 발생한다 하여 RR 회전이라고도 합니다. 코드로 구현하면 다음과 같습니다.

function rotationRR(node) {
let tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}

좌-우 회전 (LR 회전)

이중 회전은 앞서 설명한 단일 회전을 조합한 조금 더 복잡한 형태입니다. 정확히 이해하려면 회전 과정에서 일어나는 각 동작을 단계별로 짚어볼 필요가 있습니다. 먼저 좌-우 회전부터 살펴보겠습니다. 좌-우 회전은 이름 그대로 좌회전에 이어 우회전을 수행하는 조합입니다.

상태	수행 동작
	노드가 왼쪽 서브트리의 오른쪽 서브트리에 삽입되었습니다. 이로 인해 C가 불균형 노드가 되었으며, 이런 상황에서 AVL 트리는 좌-우 회전을 수행합니다.
	먼저 C의 왼쪽 서브트리에 대해 좌회전을 수행합니다. 그 결과 A가 B의 왼쪽 서브트리가 됩니다.
	노드 C는 여전히 불균형 상태입니다. 다만 이번에는 왼쪽 서브트리의 왼쪽 서브트리 때문에 불균형이 발생했습니다.
	이제 트리 전체를 우회전하여 B를 해당 서브트리의 새 루트 노드로 만듭니다. 그러면 C는 자신의 왼쪽 서브트리의 오른쪽 서브트리가 됩니다.
	트리가 이제 균형을 이룹니다.

좌회전 후 우회전을 수행한다 하여 이를 LR 회전이라고 부릅니다. 앞서 정의한 두 함수를 활용하면 다음과 같이 간단하게 구현할 수 있습니다.

function rotationLR(node) {
node.left = rotationRR(node.left);
return rotationLL(node);
}

우-좌 회전 (RL 회전)

두 번째 이중 회전 유형은 우-좌 회전입니다. 우-좌 회전은 우회전에 이어 좌회전을 수행하는 조합으로, 좌-우 회전과 정반대의 순서로 진행됩니다.

상태	수행 동작
	노드가 오른쪽 서브트리의 왼쪽 서브트리에 삽입되었습니다. 이로 인해 A가 균형인수(balance factor)가 2인 불균형 노드가 되었습니다.
	먼저 C 노드를 기준으로 우회전을 수행하여 C를 자신의 왼쪽 서브트리 B의 오른쪽 서브트리로 만듭니다. 이제 B가 A의 오른쪽 서브트리가 됩니다.
	노드 A는 여전히 오른쪽 서브트리의 오른쪽 서브트리 때문에 불균형 상태이며, 좌회전이 필요합니다.
	B를 서브트리의 새 루트 노드로 만들어 좌회전을 수행합니다. 그 결과 A는 자신의 오른쪽 서브트리 B의 왼쪽 서브트리가 됩니다.
	트리가 이제 균형을 이룹니다.

우회전 후 좌회전을 수행한다 하여 이를 RL 회전이라고 부릅니다. 역시 앞서 정의한 두 함수를 활용해 다음과 같이 구현할 수 있습니다.

function rotationRL(node) {
node.right = rotationLL(node.right);
return rotationRR(node);
}

마무리

정리하면, AVL 트리는 삽입 연산 후 어떤 노드의 균형인수 절댓값이 1을 초과하면 불균형이 발생한 방향에 따라 LL, RR, LR, RL 네 가지 회전 중 알맞은 방법을 적용합니다. 단일 회전은 한 방향으로 치우친 경우에, 이중 회전은 지그재그 형태로 삽입된 경우에 사용됩니다. 이러한 회전을 통해 AVL 트리는 탐색·삽입·삭제 연산을 항상 O(log n) 시간 복잡도로 유지할 수 있습니다.