한양과기고 에듀테크 수업도구 대시보드

한쪽으로 쏠리면 스스로 "회전"해서 균형을 되찾는 트리

보통의 이진 탐색 트리는 1, 2, 3, 4, 5…처럼 정렬된 값을 순서대로 넣으면 오른쪽으로만 길게 뻗어 사실상 연결 리스트가 되고 검색이 O(n)으로 느려진다. AVL 트리는 삽입·삭제 때마다 모든 노드의 균형 인수(왼쪽 높이 − 오른쪽 높이)를 확인해서, 그 값이 −1, 0, +1 범위를 벗어나는 순간 회전(rotation)으로 모양을 고쳐 높이를 항상 ≈ 1.44 log₂ n 이하로 유지한다. 아래에서 직접 넣어 보며 회전이 터지는 순간을 관찰하자.

1 핵심 개념 4가지

높이

노드에서 가장 먼 잎까지의 간선 수. 잎은 0, 빈 자리는 −1로 센다.

균형 인수 BF

BF = h(왼쪽) − h(오른쪽). AVL은 모든 노드에서 |BF| ≤ 1 을 강제한다.

회전

부모–자식 관계를 뒤집어 서브트리 높이를 재분배. BST 순서는 그대로 유지된다.

4가지 경우

망가진 방향에 따라 LL·RR(단일 회전), LR·RL(이중 회전)로 나뉜다.

2 직접 만들어 보는 AVL 트리

균형(회전) 켜기

트리가 비어 있다. 숫자를 넣어 루트부터 만들어 보자.

노드 수: 0 트리 높이: 0 완전 균형 시 최소 높이: 0 누적 회전 횟수: 0

💡 각 노드 오른쪽 위 작은 숫자가 균형 인수(BF)다. 빨간 테두리는 |BF| ≥ 2가 된 불균형 노드, 초록 테두리는 회전의 중심이 되는 노드다. "균형 켜기"를 끄고 1‥7 오름차순을 눌러 보면 일반 BST가 어떻게 무너지는지 보인다.

# 삽입 후 올라오면서 균형을 검사하고 필요하면 회전한다 def insert(node, key): if node is None: return Node(key) if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) node.height = 1 + max(h(node.left), h(node.right)) bf = h(node.left) - h(node.right) if bf > 1 and key < node.left.key: return rotate_right(node) # LL if bf < -1 and key > node.right.key: return rotate_left(node) # RR if bf > 1 and key > node.left.key: node.left = rotate_left(node.left); return rotate_right(node) # LR if bf < -1 and key < node.right.key: node.right = rotate_right(node.right); return rotate_left(node) # RL return node

3 네 가지 불균형과 회전

LL — 왼쪽-왼쪽 (오른쪽 단일 회전)

    z            y
   /            / \
  y     ──▶   x   z
 /
x

RR — 오른쪽-오른쪽 (왼쪽 단일 회전)

  z              y
   \            / \
    y   ──▶   z   x
     \
      x

LR — 왼쪽-오른쪽 (왼쪽→오른쪽 이중 회전)

  z          z          x
 /          /          / \
y    ──▶   x    ──▶  y   z
 \        /
  x      y

RL — 오른쪽-왼쪽 (오른쪽→왼쪽 이중 회전)

z          z            x
 \          \          / \
  y   ──▶    x    ──▶  z   y
 /            \
x              y

불균형이 처음 감지된 노드를 z, 그 무거운 쪽 자식을 y, 그 다음을 x라 하자. x가 z→y와 같은 방향이면(둘 다 왼쪽 / 둘 다 오른쪽) 한 번만 회전하면 되고, 꺾여 있으면(왼쪽 다음 오른쪽) 먼저 자식을 회전해 일직선으로 편 뒤 다시 회전한다. 회전은 서브트리 3개의 부모만 바꾸는 상수 시간 O(1) 연산이다.

4 성능

O(log n)

검색·삽입·삭제
(항상 보장)

≤ 1.44 log₂n

트리 높이 상한
(BST는 최악 n)

O(1)

회전 1번의 비용
삽입당 회전 ≤ 2회

5 자주 나오는 질문

💡 회전하면 BST의 "왼쪽 < 나 < 오른쪽" 규칙이 깨지지 않나?

안 깨진다. 회전은 중위 순회 순서를 그대로 보존하도록 설계됐다. 오른쪽 회전에서 y의 오른쪽 자식(y < ? < z인 서브트리)은 회전 후 z의 왼쪽 자식으로 옮겨가는데, 여전히 y < ? < z 위치라서 규칙이 유지된다. 시뮬레이터에서 회전 전후로 중위 순회 결과가 똑같음을 확인할 수 있다.

💡 AVL 트리 vs 레드-블랙 트리, 뭐가 다른가?

AVL이 더 엄격하게 균형을 잡아서 트리가 더 낮고 검색이 조금 빠르다. 대신 삽입·삭제 때 회전이 더 자주 일어나 쓰기가 잦으면 레드-블랙 트리가 유리하다. 그래서 읽기 위주인 DB 인덱스·인메모리 검색엔 AVL 계열이, 자바 TreeMap·리눅스 커널 스케줄러엔 레드-블랙 트리가 쓰인다.

💡 삭제할 때도 회전하나?

한다. 삭제도 BST 방식으로 노드를 지운 뒤, 루트까지 올라오며 각 노드의 BF를 검사한다. 삽입은 회전 1번(또는 이중 회전 1세트)이면 끝나지만, 삭제는 위로 올라가며 여러 번 회전이 연쇄될 수 있다(최악 O(log n)회). 그래도 전체 삭제 비용은 O(log n)이다.

💡 왜 하필 "1.44 log n"인가?

높이가 h인 AVL 트리가 가질 수 있는 최소 노드 수를 N(h)라 하면 N(h) = N(h−1) + N(h−2) + 1 이라는 피보나치 점화식이 나온다. 그래서 가장 삐뚤어진 AVL 트리("피보나치 트리")조차 높이가 노드 수의 로그에 황금비 계수 1/log₂φ ≈ 1.44를 곱한 값으로 억제된다.