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

카테고리 없음

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

kguidebook0001 2026. 2. 4. 09:24

이진 탐색 트리(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)에 따라 단순 회전 또는 이중 회전을 통해 구조를 재조정합니다.