[CS300 #048] AVL 트리 — 높이 차 1 을 회전으로 지킨다
컴퓨터공학 300 주제 시리즈의 048번째 글이다. 전체 지도는 여기.
한 줄 요약
AVL 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리 높이 차를 1 이하로 유지하는 이진 탐색 트리로, 삽입·삭제 뒤 깨진 균형을 회전으로 복구해 높이를 항상 약 1.44 log₂ n 이하로 묶어 둔다.
왜 필요한가
앞 글에서 기본 이진 탐색 트리에 0 부터 1999 까지 순서대로 넣으면 높이가 2000 이 되는 것을 봤다. 모든 연산이 O(h) 이니 사실상 연결 리스트다. 입력 순서는 우리가 고를 수 없으므로, 어떤 순서로 들어와도 높이가 O(log n) 으로 유지되는 장치가 필요하다.
AVL 트리는 그 장치를 처음 제시한 자료구조다. 1962년 Adelson-Velsky 와 Landis 가 발표했고, 이름도 두 사람의 머리글자다. 규칙이 단순하고 증명이 깔끔해서 “자가 균형 트리”를 이해하는 가장 좋은 출발점이다. 여기서 배우는 회전(rotation) 은 레드블랙 트리, 스플레이 트리, 트립 등 거의 모든 균형 트리가 공통으로 쓰는 기본 동작이다.
핵심 개념
균형 조건
각 노드의 균형 인수(balance factor) 를 높이(왼쪽) − 높이(오른쪽) 로 정의한다. AVL 트리는 모든 노드에서 균형 인수가 −1, 0, +1 중 하나다. NIST 알고리즘·자료구조 사전도 AVL 트리를 “두 서브트리 높이 차가 최대 1 인 균형 이진 탐색 트리”로 정의하고 조회·삽입·삭제를 O(log n) 으로 적는다(NIST DADS — AVL tree).
왜 높이가 O(log n) 인가
높이가 h 인 AVL 트리가 가질 수 있는 최소 노드 수를 N(h) 라고 하자. 노드 수를 최소로 하려면 한쪽 서브트리는 높이 h−1, 다른 쪽은 허용되는 가장 낮은 h−2 여야 한다.
N(h) = N(h−1) + N(h−2) + 1, N(1) = 1, N(2) = 2
피보나치 수열과 같은 꼴이다. 따라서 N(h) 는 황금비 φ ≈ 1.618 의 거듭제곱으로 자란다. 거꾸로 노드가 n 개면 h 는 log_φ n 정도, 즉 약 1.44 log₂ n 을 넘지 못한다. 완벽한 균형(log₂ n)보다 최대 44% 정도 높을 뿐이다.
회전: BST 성질을 지키며 모양만 바꾸기
회전은 부모와 자식의 위아래를 바꾸되, 중위 순회 순서(즉 정렬 순서)는 그대로 두는 연산이다. 포인터 몇 개만 바꾸므로 O(1) 이다.
오른쪽 회전 (y 기준) 왼쪽 회전 (x 기준)
y x x y
/ \ / \ / \ / \
x C ──▶ A y A y ──▶ x C
/ \ / \ / \ / \
A B B C B C A B
중위 순서는 둘 다 A x B y C 로 같다
B 서브트리가 x 의 오른쪽에서 y 의 왼쪽으로 옮겨 가는 것이 핵심이다. B 의 키는 x 보다 크고 y 보다 작으니 어느 자리에서든 BST 성질을 만족한다.
불균형의 네 가지 모양
삽입 후 루트 쪽으로 올라가며 높이를 갱신하다가 균형 인수가 ±2 인 노드 z 를 처음 만나면, z 아래 어느 쪽이 무거운지에 따라 네 경우로 나뉜다.
| 경우 | 모양 | 처리 |
|---|---|---|
| LL | 왼쪽 자식의 왼쪽이 무거움 | z 를 오른쪽 회전 1회 |
| RR | 오른쪽 자식의 오른쪽이 무거움 | z 를 왼쪽 회전 1회 |
| LR | 왼쪽 자식의 오른쪽이 무거움 | 왼쪽 자식을 왼쪽 회전 → z 를 오른쪽 회전 |
| RL | 오른쪽 자식의 왼쪽이 무거움 | 오른쪽 자식을 오른쪽 회전 → z 를 왼쪽 회전 |
LR 예: 30, 10, 20 순서로 삽입
30 30 20
/ / / \
10 ──▶ 20 ──▶ 10 30
\ /
20 10
(10 왼쪽 회전) (30 오른쪽 회전)
삽입에서는 이 복구를 한 번(단일 또는 이중 회전) 하면 그 위 조상들의 높이가 삽입 전과 같아져 더 올라갈 필요가 없다. 삭제는 다르다. 회전 후에도 서브트리 높이가 1 줄 수 있어서 루트까지 O(log n) 번 회전이 이어질 수 있다.
AVL 과 레드블랙 트리
| 항목 | AVL | 레드블랙 |
|---|---|---|
| 균형 조건 | 높이 차 ≤ 1 (엄격) | 검은 높이 같음, 빨강 연속 금지 (느슨) |
| 최대 높이 | 약 1.44 log₂ n | 약 2 log₂ n |
| 탐색 | 더 빠른 편 (트리가 낮음) | 약간 느릴 수 있음 |
| 삭제 시 회전 | O(log n) 까지 | 최대 3회 |
| 노드 추가 정보 | 높이(또는 균형 인수 2비트) | 색 1비트 |
조회가 압도적으로 많으면 AVL 이, 갱신이 잦으면 레드블랙이 유리하다는 것이 교과서적 정리다. 실제로 범용 라이브러리는 대부분 레드블랙을 택했다. 다음 글에서 다룬다.
직접 해 보기
높이를 노드에 저장하는 AVL 삽입을 구현하고, 정렬된 입력에서 높이가 어떻게 유지되는지 본다. check 함수는 모든 노드에서 AVL 성질과 BST 성질을 검사한다.
import random, math
class Node:
__slots__ = ("key", "left", "right", "h")
def __init__(self, key):
self.key, self.left, self.right, self.h = key, None, None, 1
def h(n): return n.h if n else 0
def bf(n): return h(n.left) - h(n.right) # 균형 인수
def fix(n): n.h = 1 + max(h(n.left), h(n.right))
def rot_right(y):
x = y.left
y.left = x.right
x.right = y
fix(y); fix(x)
return x
def rot_left(x):
y = x.right
x.right = y.left
y.left = x
fix(x); fix(y)
return y
rotations = 0
def rebalance(n):
global rotations
fix(n)
if bf(n) > 1: # 왼쪽이 무겁다
if bf(n.left) < 0: # LR: 먼저 왼쪽 자식을 왼쪽 회전
n.left = rot_left(n.left); rotations += 1
rotations += 1
return rot_right(n) # LL
if bf(n) < -1: # 오른쪽이 무겁다
if bf(n.right) > 0: # RL
n.right = rot_right(n.right); rotations += 1
rotations += 1
return rot_left(n) # RR
return n
def insert(n, key):
if n is None:
return Node(key)
if key < n.key: n.left = insert(n.left, key)
elif key > n.key: n.right = insert(n.right, key)
else: return n
return rebalance(n)
def check(n): # AVL 성질과 BST 성질 검사, 높이 반환
if n is None: return 0
lh, rh = check(n.left), check(n.right)
assert abs(lh - rh) <= 1 and n.h == 1 + max(lh, rh)
assert (n.left is None or n.left.key < n.key) and (n.right is None or n.right.key > n.key)
return n.h
root = None
for k in [10, 20, 30]: # RR 상황 → 왼쪽 회전 1번
root = insert(root, k)
print("10,20,30 삽입 후 루트:", root.key, "왼:", root.left.key, "오:", root.right.key)
for N in (1_000, 100_000):
root, rotations = None, 0
for k in range(N): # 정렬된 순서: 기본 BST 라면 높이 N
root = insert(root, k)
print(f"N={N:>7,} 높이={check(root):>2} log2(N)={math.log2(N):5.1f} "
f"1.44*log2(N+2)={1.44*math.log2(N+2):5.1f} 회전={rotations:,}")
random.seed(3)
keys = random.sample(range(10**6), 100_000)
root, rotations = None, 0
for k in keys:
root = insert(root, k)
print(f"무작위 100,000개 높이={check(root)} 회전={rotations:,}")
10,20,30 삽입 후 루트: 20 왼: 10 오: 30
N= 1,000 높이=10 log2(N)= 10.0 1.44*log2(N+2)= 14.4 회전=990
N=100,000 높이=17 log2(N)= 16.6 1.44*log2(N+2)= 23.9 회전=99,983
무작위 100,000개 높이=20 회전=69,512
(높이는 노드 수 기준이고, 회전 수는 이중 회전을 2회로 센 값이다.)
정렬된 10만 개를 넣어도 높이는 17 이다. 기본 BST 였다면 10만이었다. 정렬 입력에서는 오히려 거의 완벽한 균형(log₂ n ≈ 16.6)이 나오는데, 매번 오른쪽 끝에 붙고 그때마다 회전이 일어나 꽉 찬 트리처럼 다듬어지기 때문이다. 무작위 입력은 높이 20 으로 이론 상한 23.9 아래에 있다. check 가 10만 개 노드 모두에서 통과했으므로 회전이 BST 성질을 깨지 않았다는 것도 확인된다.
현업에서는
- 직접 구현할 일은 드물다. 대부분의 언어 표준 라이브러리 순서 맵은 레드블랙 트리나 B-트리다. AVL 은 조회 비중이 높은 메모리 내 인덱스를 직접 만들 때 후보가 되는 정도다.
- 회전은 어디서나 나온다. 레드블랙 트리의 삽입·삭제, 스플레이 트리, 트립, 구간 트리 같은 증강 트리가 모두 이 글의 두 회전을 쓴다. 회전을 손으로 그릴 수 있으면 다른 균형 트리 코드도 읽힌다.
- 증강(augmentation) 정보 유지. 노드에 높이 대신 “서브트리 크기”나 “서브트리 합”을 저장하면 k 번째 원소 찾기, 구간 합 같은 질의를 O(log n) 에 할 수 있다. 회전 때
fix처럼 그 값만 다시 계산하면 된다. 위 코드의fix가 그 틀이다. - 면접과 시험. “이 순서로 넣은 뒤의 AVL 트리를 그려라”는 단골 문제다. 아래 확인 문제로 손에 익혀 두면 좋다.
확인 문제
- 균형 인수가 +2 인 노드의 왼쪽 자식 균형 인수가 −1 이면 어떤 경우이고, 어떤 회전이 필요한가?
- 빈 AVL 트리에 3, 2, 1 을 순서대로 넣으면 최종 루트는?
- 높이(노드 수 기준) 4 인 AVL 트리의 최소 노드 수는?
- 회전이 BST 성질을 깨지 않는 이유를 한 문장으로 쓰라.
- 삽입은 회전 1번(단일 또는 이중)으로 끝나는데 삭제는 여러 번 필요할 수 있는 이유는?
풀이
- LR 경우. 왼쪽 자식을 왼쪽 회전한 뒤, 그 노드를 오른쪽 회전한다.
-
- (LL 경우라 3 에서 오른쪽 회전.)
- N(1)=1, N(2)=2, N(3)=N(2)+N(1)+1=4, N(4)=N(3)+N(2)+1=7. 7개.
- 회전 전후의 중위 순회 순서(A x B y C)가 같기 때문이다.
- 삽입 복구 후에는 그 서브트리 높이가 삽입 전과 같아지지만, 삭제 복구 후에는 서브트리 높이가 1 줄어든 채로 남을 수 있어 위쪽 조상의 균형이 다시 깨질 수 있다.
더 읽을거리 (References)
- NIST Dictionary of Algorithms and Data Structures, AVL tree
- MIT OpenCourseWare 6.006 (Spring 2020), Lecture 7: Binary Trees, Part 2: AVL
- G. M. Adelson-Velsky, E. M. Landis, “An algorithm for the organization of information”, Soviet Mathematics Doklady 3, 1962
- Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998 — 6.2.3 Balanced Trees