AVL 트리 균형 원리 (회전, 높이 조절)

이진 탐색 트리(BST, Binary Search Tree)는 효율적인 데이터 검색을 위해 고안된 훌륭한 자료구조입니다. 하지만 데이터가 정렬된 상태로 순차적으로 입력될 경우, 트리가 한쪽으로 치우치는 편향(Skewed) 현상이 발생하여 최악의 경우 연결 리스트와 동일한 $O(N)$의 시간 복잡도를 가지게 됩니다. 이러한 치명적인 약점을 보완하기 위해 등장한 것이 바로 AVL 트리(Adelson-Velsky and Landis Tree)입니다. AVL 트리는 스스로 균형을 잡는(Self-Balancing) 최초의 알고리즘으로, 삽입과 삭제가 일어날 때마다 트리의 높이 균형을 맞추어 항상 $O(\log N)$의 성능을 보장합니다. 본 글에서는 AVL 트리가 어떻게 균형 인수(Balance Factor)를 계산하고, 회전(Rotation)을 통해 구조를 재조정하는지 기술적으로 심층 분석합니다.

1. AVL 트리의 핵심: 균형 인수 (Balance Factor)

AVL 트리는 모든 노드에 대해 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1 이하여야 한다는 엄격한 규칙을 가집니다. 이 규칙을 준수하는지 판단하기 위해 각 노드는 균형 인수(BF, Balance Factor)라는 값을 관리합니다.

1-1. 균형 인수 계산 공식

균형 인수는 다음과 같은 공식으로 정의됩니다.

$$BF(Node) = Height(Left Subtree) - Height(Right Subtree)$$

AVL 트리의 모든 노드는 $BF$ 값이 -1, 0, 1 중 하나여야 합니다. 만약 특정 노드의 $|BF| \ge 2$가 되는 순간, 해당 노드를 중심으로 균형이 깨진 것으로 간주하고 리밸런싱(Rebalancing), 즉 회전 연산을 수행합니다.

2. 균형을 회복하는 4가지 회전(Rotation) 알고리즘

균형이 깨지는 상황은 데이터가 삽입된 위치에 따라 4가지 케이스(LL, RR, LR, RL)로 분류됩니다. 각 상황에 맞춰 적절한 회전을 수행하여 트리의 높이를 조정합니다.

2-1. LL (Left-Left) Case와 단순 우회전

불균형이 발생한 노드의 왼쪽 자식의 왼쪽 서브 트리에 노드가 삽입되어 $BF$가 양수로 커진 상황입니다. 이때는 우회전(Right Rotation)을 1회 수행하여 해결합니다.

해결: 불균형 노드를 오른쪽으로 끌어내리고, 왼쪽 자식을 새로운 부모로 승격시킵니다.

2-2. RR (Right-Right) Case와 단순 좌회전

불균형 노드의 오른쪽 자식의 오른쪽 서브 트리에 노드가 삽입되어 $BF$가 음수로 작아진 상황입니다. 이때는 좌회전(Left Rotation)을 1회 수행합니다.

해결: 불균형 노드를 왼쪽으로 끌어내리고, 오른쪽 자식을 새로운 부모로 승격시킵니다.

2-3. LR (Left-Right) Case와 이중 회전

불균형 노드의 왼쪽 자식의 오른쪽 서브 트리에 노드가 삽입된 경우입니다. 단순 회전으로는 해결되지 않으며, 두 번의 회전이 필요합니다.

1단계: 왼쪽 자식을 기준으로 좌회전을 수행하여 LL 상태로 만듭니다.
2단계: 불균형 노드를 기준으로 우회전을 수행하여 균형을 맞춥니다.

2-4. RL (Right-Left) Case와 이중 회전

불균형 노드의 오른쪽 자식의 왼쪽 서브 트리에 노드가 삽입된 경우입니다.

1단계: 오른쪽 자식을 기준으로 우회전을 수행하여 RR 상태로 만듭니다.
2단계: 불균형 노드를 기준으로 좌회전을 수행하여 균형을 맞춥니다.

3. 파이썬(Python) 구현: 우회전 로직 예시

이론적으로 복잡해 보이지만, 포인터(참조) 변경을 통해 $O(1)$ 시간 내에 회전이 가능합니다. 다음은 LL 케이스를 해결하는 우회전(Right Rotation)의 구현 예시입니다.


class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def get_height(node):
    if not node:
        return 0
    return node.height

def right_rotate(y):
    """
    y 노드를 기준으로 우회전 수행
       y           x
      / \         / \
     x   T3  ->  T1  y
    / \             / \
   T1  T2          T2 T3
    """
    x = y.left
    T2 = x.right

    # 회전 수행 (참조 변경)
    x.right = y
    y.left = T2

    # 높이 갱신 (부모가 된 x와 자식이 된 y 모두 갱신 필요)
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))

    # 새로운 루트 노드 x 반환
    return x

위 코드에서 볼 수 있듯이, 회전 연산은 노드의 값 자체를 바꾸는 것이 아니라 링크(Link)의 연결 구조를 변경하고 높이 값을 갱신하는 방식으로 동작합니다.

[핵심 요약 : AVL 트리의 원리]
1. 목적: 편향 이진 트리의 $O(N)$ 성능 저하를 막고, 항상 $O(\log N)$의 검색/삽입/삭제 속도를 보장합니다.
2. 판단 기준: 모든 노드의 균형 인수(BF) 절댓값이 1 이하($-1, 0, 1$)여야 합니다.
3. 해결책: 균형이 깨지면 문제의 유형(LL, RR, LR, RL)에 따라 단순 회전 또는 이중 회전을 통해 구조를 재조정합니다.

kguidebook0001 님의 블로그