AVL 트리 — 회전으로 균형을 유지하는 원리
BST가 편향되면 O(n)이 되는 문제, 어떻게 하면 항상 O(log n)을 보장할 수 있을까요?
AVL 트리란
AVL 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1 인 자가 균형 이진 탐색 트리입니다. 1962년에 Adelson-Velsky와 Landis가 발명했습니다.
핵심 개념은 균형 인수(Balance Factor) 입니다.
Balance Factor = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
- BF가 -1, 0, 1이면 균형 상태
- BF가 -2 이하 또는 2 이상이면 ** 불균형** → 회전이 필요
왜 필요한가
일반 BST는 편향되면 O(n)이 됩니다. AVL 트리는 삽입/삭제 후 불균형이 감지되면 ** 회전 **으로 즉시 균형을 맞추므로, ** 항상 O(log n)**을 보장합니다.
편향 BST (O(n)): AVL 트리 (O(log n)):
1 3
\ / \
2 2 4
\ / \
3 1 5
\
4
\
5
노드 구조
class AVLNode<T extends Comparable<T>> {
T value;
AVLNode<T> left, right;
int height; // 노드의 높이
AVLNode(T value) {
this.value = value;
this.height = 1; // 리프 노드의 높이는 1
}
}
유틸리티 메서드
int height(AVLNode<T> node) {
return (node == null) ? 0 : node.height;
}
int balanceFactor(AVLNode<T> node) {
return height(node.left) - height(node.right);
}
void updateHeight(AVLNode<T> node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
회전 — 균형을 맞추는 핵심 연산
불균형이 발생하면 네 가지 케이스 중 하나에 해당하며, 각각에 맞는 회전을 수행합니다.
오른쪽 회전 (Right Rotation) — LL 케이스
왼쪽 자식의 왼쪽에 삽입되어 불균형이 생긴 경우입니다.
z (BF=2) y
/ \ / \
y T4 → x z
/ \ / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
AVLNode<T> rotateRight(AVLNode<T> z) {
AVLNode<T> y = z.left;
AVLNode<T> T3 = y.right;
// 회전 수행
y.right = z;
z.left = T3;
// 높이 업데이트 (z를 먼저, y가 z의 부모이므로)
updateHeight(z);
updateHeight(y);
return y; // 새로운 루트
}
왼쪽 회전 (Left Rotation) — RR 케이스
오른쪽 자식의 오른쪽에 삽입되어 불균형이 생긴 경우입니다.
z (BF=-2) y
/ \ / \
T1 y → z x
/ \ / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
AVLNode<T> rotateLeft(AVLNode<T> z) {
AVLNode<T> y = z.right;
AVLNode<T> T2 = y.left;
y.left = z;
z.right = T2;
updateHeight(z);
updateHeight(y);
return y;
}
LR 케이스 — 왼쪽 회전 후 오른쪽 회전
왼쪽 자식의 ** 오른쪽 **에 삽입된 경우입니다. 단순 오른쪽 회전으로는 해결되지 않습니다.
z (BF=2) z x
/ \ / \ / \
y T4 → x T4 → y z
/ \ / \ / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
원래 왼쪽 회전(y) 오른쪽 회전(z)
// LR 케이스: 왼쪽 자식을 왼쪽 회전 → 전체를 오른쪽 회전
node.left = rotateLeft(node.left);
return rotateRight(node);
RL 케이스 — 오른쪽 회전 후 왼쪽 회전
오른쪽 자식의 ** 왼쪽 **에 삽입된 경우입니다. LR의 대칭입니다.
// RL 케이스: 오른쪽 자식을 오른쪽 회전 → 전체를 왼쪽 회전
node.right = rotateRight(node.right);
return rotateLeft(node);
삽입
AVLNode<T> insert(AVLNode<T> node, T value) {
// 1. 일반 BST 삽입
if (node == null) return new AVLNode<>(value);
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node.left = insert(node.left, value);
} else if (cmp > 0) {
node.right = insert(node.right, value);
} else {
return node; // 중복 허용하지 않음
}
// 2. 높이 업데이트
updateHeight(node);
// 3. 균형 확인 및 회전
int bf = balanceFactor(node);
// LL 케이스
if (bf > 1 && value.compareTo(node.left.value) < 0) {
return rotateRight(node);
}
// RR 케이스
if (bf < -1 && value.compareTo(node.right.value) > 0) {
return rotateLeft(node);
}
// LR 케이스
if (bf > 1 && value.compareTo(node.left.value) > 0) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
// RL 케이스
if (bf < -1 && value.compareTo(node.right.value) < 0) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
삽입 예시
1, 2, 3을 순서대로 삽입하면:
삽입 1: 1 삽입 2: 1 (BF=-2) 회전 후: 2
\ / \
2 1 3
\
3
정렬된 데이터를 삽입해도 균형이 유지됩니다.
삭제
삭제 후에도 균형 확인과 회전이 필요합니다. BST 삭제 로직에 균형 유지 코드를 추가합니다.
AVLNode<T> delete(AVLNode<T> node, T value) {
if (node == null) return null;
int cmp = value.compareTo(node.value);
if (cmp < 0) {
node.left = delete(node.left, value);
} else if (cmp > 0) {
node.right = delete(node.right, value);
} else {
// 삭제 대상 발견
if (node.left == null) return node.right;
if (node.right == null) return node.left;
// 자식이 2개: 중위 후속자로 대체
AVLNode<T> successor = findMin(node.right);
node.value = successor.value;
node.right = delete(node.right, successor.value);
}
updateHeight(node);
// 균형 확인 및 회전 (삽입과 동일한 로직)
int bf = balanceFactor(node);
if (bf > 1 && balanceFactor(node.left) >= 0) return rotateRight(node);
if (bf > 1 && balanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (bf < -1 && balanceFactor(node.right) <= 0) return rotateLeft(node);
if (bf < -1 && balanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
삭제에서는 삽입과 달리 ** 연쇄 회전 **이 발생할 수 있습니다. 삭제로 인해 여러 조상 노드의 균형이 깨질 수 있기 때문입니다.
AVL 트리 vs Red-Black 트리
| 특성 | AVL 트리 | Red-Black 트리 |
|---|---|---|
| 균형 조건 | 높이 차이 ≤ 1 (엄격) | 색상 규칙 (느슨) |
| 최대 높이 | ~1.44 log n | ~2 log n |
| 검색 성능 | 더 빠름 | 약간 느림 |
| 삽입/삭제 | 회전 많음 (최대 O(log n)) | 회전 적음 (최대 2~3번) |
| 사용 사례 | 읽기 중심 | 읽기/쓰기 균형 |
실제 사용
- Java TreeMap/TreeSet: Red-Black 트리 사용
- **Linux CFS 스케줄러 **: Red-Black 트리 사용
- ** 데이터베이스 인메모리 인덱스 **: AVL 트리가 유리할 수 있음
- C++ STL map: Red-Black 트리 사용
Red-Black 트리가 더 널리 쓰이는 이유는 삽입/삭제가 빈번한 실무 환경에서 회전 횟수가 적기 때문입니다.
AVL 트리의 수학적 성질
높이 h인 AVL 트리의 최소 노드 수를 N(h)라 하면:
N(0) = 1
N(1) = 2
N(h) = N(h-1) + N(h-2) + 1
이는 피보나치 수와 유사하며, 역으로 n개의 노드를 가진 AVL 트리의 최대 높이는 약 1.44 × log₂(n) 입니다.
이것이 AVL 트리가 "높이 최적화된" 트리인 이유입니다. Red-Black 트리(~2 log n)보다 높이가 낮으므로, 읽기 연산이 더 빠릅니다.
정리
- AVL 트리는 균형 인수(BF)가 -1, 0, 1 인 자가 균형 BST입니다.
- 불균형 시 LL, RR, LR, RL 네 가지 회전으로 균형을 맞춥니다.
- ** 검색 **은 Red-Black 트리보다 빠르지만, ** 삽입/삭제 **는 회전이 더 많이 필요합니다.
- 실무에서는 Red-Black 트리가 더 많이 사용되지만, 읽기 중심 워크로드에서는 AVL이 유리할 수 있습니다.
- 회전의 핵심은 BST 속성을 유지하면서 높이를 줄이는 것 입니다.
댓글 로딩 중...