AVL 트리 완벽 가이드 | 자가 균형 이진 탐색 트리 구현과 회전
이 글의 핵심
AVL 트리 완벽 가이드. 자가 균형 이진 탐색 트리의 원리, LL/RR/LR/RL 회전 알고리즘, 삽입/삭제 구현, O(log n) 시간 복잡도 보장 방법을 설명합니다.
들어가며
AVL 트리는 자가 균형 이진 탐색 트리입니다. 삽입/삭제 시 자동으로 균형을 맞춰 항상 O(log n) 시간 복잡도를 보장합니다.
비유로 말씀드리면, 일반 이진 탐색 트리는 한쪽으로 기울어질 수 있는 나무이고, AVL 트리는 자동으로 균형을 잡는 나무입니다. 한쪽이 무거워지면 자동으로 회전하여 균형을 맞춥니다.
이 글을 읽으면
- AVL 트리의 원리를 이해합니다
- LL, RR, LR, RL 회전을 파악합니다
- 삽입과 삭제를 구현합니다
- Red-Black 트리와 비교합니다
목차
AVL 트리 기초
이진 탐색 트리 (BST) 문제
일반 BST의 문제:
삽입 순서: 1, 2, 3, 4, 5
1
\
2
\
3
\
4
\
5
높이: 5 (편향 트리)
검색 시간: O(n)AVL 트리 해결
자동 균형:
삽입 순서: 1, 2, 3, 4, 5
2
/ \
1 4
/ \
3 5
높이: 3 (균형 트리)
검색 시간: O(log n)균형 인수 (Balance Factor)
정의:
BF(노드) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이AVL 트리 조건:
모든 노드의 BF는 -1, 0, 1 중 하나
BF = -2 또는 2 → 회전 필요예시:
10 (BF=0)
/ \
5 15 (BF=-1)
/ \ \
3 7 20
BF(10) = 2 - 2 = 0
BF(5) = 1 - 1 = 0
BF(15) = 0 - 1 = -1회전 알고리즘
4가지 회전 유형
| 유형 | 상황 | 회전 |
|---|---|---|
| LL | 왼쪽-왼쪽 편향 | 오른쪽 회전 |
| RR | 오른쪽-오른쪽 편향 | 왼쪽 회전 |
| LR | 왼쪽-오른쪽 편향 | 왼쪽 후 오른쪽 |
| RL | 오른쪽-왼쪽 편향 | 오른쪽 후 왼쪽 |
LL 회전 (오른쪽 회전)
상황:
30 (BF=2)
/
20 (BF=1)
/
10
왼쪽이 무거움 → 오른쪽 회전회전 후:
20
/ \
10 30
균형 회복!코드:
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
// 회전
x->right = y;
y->left = T2;
// 높이 업데이트
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x; // 새 루트
}RR 회전 (왼쪽 회전)
상황:
10 (BF=-2)
\
20 (BF=-1)
\
30
오른쪽이 무거움 → 왼쪽 회전회전 후:
20
/ \
10 30
균형 회복!코드:
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
// 회전
y->left = x;
x->right = T2;
// 높이 업데이트
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y; // 새 루트
}LR 회전 (왼쪽-오른쪽 회전)
상황:
30 (BF=2)
/
10 (BF=-1)
\
20
왼쪽-오른쪽 편향 → 왼쪽 회전 후 오른쪽 회전1단계: 왼쪽 회전
30
/
20
/
102단계: 오른쪽 회전
20
/ \
10 30코드:
Node* leftRightRotate(Node* node) {
node->left = leftRotate(node->left); // 1단계
return rightRotate(node); // 2단계
}RL 회전 (오른쪽-왼쪽 회전)
상황:
10 (BF=-2)
\
30 (BF=1)
/
20
오른쪽-왼쪽 편향 → 오른쪽 회전 후 왼쪽 회전1단계: 오른쪽 회전
10
\
20
\
302단계: 왼쪽 회전
20
/ \
10 30삽입 구현
전체 코드
struct Node {
int key;
Node* left;
Node* right;
int height;
Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};
int height(Node* node) {
return node ? node->height : 0;
}
int getBalance(Node* node) {
return node ? height(node->left) - height(node->right) : 0;
}
Node* insert(Node* node, int key) {
// 1. 일반 BST 삽입
if (!node) return new Node(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node; // 중복 키
// 2. 높이 업데이트
node->height = 1 + max(height(node->left), height(node->right));
// 3. 균형 인수 계산
int balance = getBalance(node);
// 4. 불균형 처리
// LL 케이스
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// RR 케이스
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// LR 케이스
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL 케이스
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}성능 비교
AVL vs 일반 BST
| 작업 | 일반 BST (최악) | AVL 트리 |
|---|---|---|
| 검색 | O(n) | O(log n) |
| 삽입 | O(n) | O(log n) |
| 삭제 | O(n) | O(log n) |
AVL vs Red-Black 트리
| 특성 | AVL 트리 | Red-Black 트리 |
|---|---|---|
| 균형 | 엄격 (BF ≤ 1) | 느슨 (높이 2배 이내) |
| 검색 | 더 빠름 | 느림 |
| 삽입 | 느림 | 더 빠름 |
| 삭제 | 느림 | 더 빠름 |
| 회전 횟수 | 많음 (최대 2회) | 적음 (최대 3회) |
| 사용 | 검색 많을 때 | 삽입/삭제 많을 때 |
실제 벤치마크
// 100만 개 삽입 + 100만 회 검색
AVL 트리:
삽입: 450ms
검색: 180ms
총: 630ms
Red-Black 트리:
삽입: 320ms
검색: 220ms
총: 540ms
일반 BST (편향):
삽입: 200ms
검색: 50,000ms (50초!)
총: 50,200ms실전 활용
1. 데이터베이스 인덱스
// B-Tree의 기초가 되는 개념
class DatabaseIndex {
AVLTree<int, Record*> index;
public:
void insert(int key, Record* record) {
index.insert(key, record);
}
Record* find(int key) {
return index.search(key); // O(log n)
}
};2. 우선순위 큐 (대안)
// Heap 대신 AVL 트리 사용 가능
class PriorityQueue {
AVLTree<int> tree;
public:
void push(int value) {
tree.insert(value);
}
int top() {
return tree.findMin(); // 가장 작은 값
}
void pop() {
tree.deleteMin();
}
};3. 범위 쿼리
// 특정 범위의 값 찾기
vector<int> rangeQuery(Node* root, int low, int high) {
vector<int> result;
function<void(Node*)> inorder = [&](Node* node) {
if (!node) return;
if (node->key > low)
inorder(node->left);
if (node->key >= low && node->key <= high)
result.push_back(node->key);
if (node->key < high)
inorder(node->right);
};
inorder(root);
return result;
}
// 예시: 10 이상 50 이하 값 찾기
auto values = rangeQuery(root, 10, 50);트러블슈팅
1. 회전 후에도 불균형
문제:
// 회전 후에도 BF가 2원인:
- 잘못된 회전 유형 선택
- 높이 업데이트 누락
해결:
// 회전 후 반드시 높이 업데이트
node->height = 1 + max(height(node->left), height(node->right));2. 메모리 누수
문제:
// 삭제 시 메모리 해제 안함
Node* deleteNode(Node* root, int key) {
// ... 노드 찾기
// delete 호출 안함!
}해결:
Node* deleteNode(Node* root, int key) {
// ... 노드 찾기
if (노드를 삭제해야 함) {
Node* temp = node;
// ... 재연결
delete temp; // 메모리 해제
}
return root;
}3. 중복 키 처리
문제:
// 중복 키를 어떻게 처리?
insert(root, 10);
insert(root, 10); // 중복!해결 1: 무시
if (key == node->key)
return node; // 아무것도 안함해결 2: 카운트
struct Node {
int key;
int count; // 중복 횟수
// ...
};
if (key == node->key) {
node->count++;
return node;
}마무리
AVL 트리는 항상 O(log n)을 보장하는 강력한 자료구조입니다.
핵심 요약:
- 균형 인수: -1, 0, 1만 허용
- 4가지 회전: LL, RR, LR, RL
- 시간 복잡도: 검색/삽입/삭제 모두 O(log n)
- 공간 복잡도: O(n)
장점:
- 항상 균형 유지
- 검색 성능 최고
- 예측 가능한 성능
단점:
- 구현 복잡
- 삽입/삭제 시 회전 오버헤드
- Red-Black 트리보다 느린 삽입/삭제
사용 시기:
- 검색이 매우 많을 때
- 예측 가능한 성능 필요
- 데이터베이스 인덱스
다음 단계:
- Red-Black 트리
- B-Tree
- 해시 테이블
AVL 트리를 마스터하면 고급 자료구조를 이해하는 기초가 됩니다!