AVL 트리란 무엇인가?
AVL 트리는 자가 균형(self-balancing) 이진 탐색 트리의 대표적인 예입니다. 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 절대 1을 초과하지 않도록 스스로 균형을 유지하는 것이 특징입니다. 덕분에 트리가 한쪽으로 치우쳐 탐색 성능이 최악으로(O(n)) 떨어지는 것을 방지하고, 항상 O(log n) 수준의 검색·삽입·삭제 성능을 보장할 수 있습니다.
트리 회전(Tree Rotation)의 원리
트리 회전은 노드 간의 정렬 순서를 그대로 유지하면서 트리의 구조만 변경하는 연산입니다. 회전이 일어나면 한 노드는 위로 올라가고 다른 한 노드는 아래로 내려갑니다. 작은 서브트리는 아래로, 큰 서브트리는 위로 옮겨 전체 트리의 높이를 줄임으로써 다양한 트리 연산의 성능을 향상시키는 데 활용됩니다.
회전의 방향은 노드들이 어느 쪽으로 밀리는지에 따라 결정되며, 어떤 자식이 루트 자리를 대체하느냐로 설명하기도 합니다. 아래 소개하는 C++ 프로그램은 이러한 AVL 트리를 직접 구현한 예제입니다.
주요 함수 설명
- height(avl *) : 주어진 AVL 트리의 높이를 계산합니다.
- difference(avl *) : 주어진 트리의 왼쪽·오른쪽 서브트리 높이 차이(균형 인수)를 계산합니다.
- rr_rotat(avl *) : 오른쪽-오른쪽(RR) 회전으로, 오른쪽 회전 두 번을 조합한 형태입니다.
- ll_rotat(avl *) : 왼쪽-왼쪽(LL) 회전으로, 왼쪽 회전 두 번을 조합한 형태입니다.
- lr_rotat(avl*) : 왼쪽-오른쪽(LR) 회전으로, 왼쪽 회전 후 오른쪽 회전을 조합한 형태입니다.
- rl_rotat(avl *) : 오른쪽-왼쪽(RL) 회전으로, 오른쪽 회전 후 왼쪽 회전을 조합한 형태입니다.
- balance(avl *) : 균형 인수를 확인하여 트리 전체에 균형 연산을 수행합니다.
- insert(avl*, int) : 삽입 연산을 수행하며, 이 함수를 통해 트리에 값을 추가합니다.
- show(avl*, int) : 트리의 값들을 시각적으로 출력합니다.
- inorder(avl *) : 중위 순회(in-order) 방식으로 트리를 탐색합니다.
- preorder(avl *) : 전위 순회(pre-order) 방식으로 트리를 탐색합니다.
- postorder(avl*) : 후위 순회(post-order) 방식으로 트리를 탐색합니다.
예제 코드
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define pow2(n) (1 << (n))
using namespace std;
struct avl {
int d;
struct avl *l;
struct avl *r;
}*r;
class avl_tree {
public:
int height(avl *);
int difference(avl *);
avl *rr_rotat(avl *);
avl *ll_rotat(avl *);
avl *lr_rotat(avl*);
avl *rl_rotat(avl *);
avl * balance(avl *);
avl * insert(avl*, int);
void show(avl*, int);
void inorder(avl *);
void preorder(avl *);
void postorder(avl*);
avl_tree() {
r = NULL;
}
};
int avl_tree::height(avl *t) {
int h = 0;
if (t != NULL) {
int l_height = height(t->l);
int r_height = height(t->r);
int max_height = max(l_height, r_height);
h = max_height + 1;
}
return h;
}
int avl_tree::difference(avl *t) {
int l_height = height(t->l);
int r_height = height(t->r);
int b_factor = l_height - r_height;
return b_factor;
}
avl *avl_tree::rr_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = t->l;
t->l = parent;
cout<<"Right-Right Rotation";
return t;
}
avl *avl_tree::ll_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = t->r;
t->r = parent;
cout<<"Left-Left Rotation";
return t;
}
avl *avl_tree::lr_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = rr_rotat(t);
cout<<"Left-Right Rotation";
return ll_rotat(parent);
}
avl *avl_tree::rl_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = ll_rotat(t);
cout<<"Right-Left Rotation";
return rr_rotat(parent);
}
avl *avl_tree::balance(avl *t) {
int bal_factor = difference(t);
if (bal_factor > 1) {
if (difference(t->l) > 0)
t = ll_rotat(t);
else
t = lr_rotat(t);
} else if (bal_factor < -1) {
if (difference(t->r) > 0)
t = rl_rotat(t);
else
t = rr_rotat(t);
}
return t;
}
avl *avl_tree::insert(avl *r, int v) {
if (r == NULL) {
r = new avl;
r->d = v;
r->l = NULL;
r->r = NULL;
return r;
} else if (v< r->d) {
r->l = insert(r->l, v);
r = balance(r);
} else if (v >= r->d) {
r->r = insert(r->r, v);
r = balance(r);
} return r;
}
void avl_tree::show(avl *p, int l) {
int i;
if (p != NULL) {
show(p->r, l+ 1);
cout<<" ";
if (p == r)
cout << "Root -> ";
for (i = 0; i < l&& p != r; i++)
cout << " ";
cout << p->d;
show(p->l, l + 1);
}
}
void avl_tree::inorder(avl *t) {
if (t == NULL)
return;
inorder(t->l);
cout << t->d << " ";
inorder(t->r);
}
void avl_tree::preorder(avl *t) {
if (t == NULL)
return;
cout << t->d << " ";
preorder(t->l);
preorder(t->r);
}
void avl_tree::postorder(avl *t) {
if (t == NULL)
return;
postorder(t ->l);
postorder(t ->r);
cout << t->d << " ";
}
int main() {
int c, i;
avl_tree avl;
while (1) {
cout << "1.Insert Element into the tree" << endl;
cout << "2.show Balanced AVL Tree" << endl;
cout << "3.InOrder traversal" << endl;
cout << "4.PreOrder traversal" << endl;
cout << "5.PostOrder traversal" << endl;
cout << "6.Exit" << endl;
cout << "Enter your Choice: ";
cin >> c;
switch (c) {
case 1:
cout << "Enter value to be inserted: ";
cin >> i;
r = avl.insert(r, i);
break;
case 2:
if (r == NULL) {
cout << "Tree is Empty" << endl;
continue;
}
cout << "Balanced AVL Tree:" << endl;
avl.show(r, 1);
cout<<endl;
break;
case 3:
cout << "Inorder Traversal:" << endl;
avl.inorder(r);
cout << endl;
break;
case 4:
cout << "Preorder Traversal:" << endl;
avl.preorder(r);
cout << endl;
break;
case 5:
cout << "Postorder Traversal:" << endl;
avl.postorder(r);
cout << endl;
break;
case 6:
exit(1);
break;
default:
cout << "Wrong Choice" << endl;
}
}
return 0;
}실행 결과
프로그램을 실행하면 메뉴 기반 콘솔 화면이 나타납니다. 값들을 차례로 삽입하면 필요할 때마다 회전 연산이 자동으로 수행되어 트리의 균형이 유지됩니다. 아래 예시에서는 4를 삽입할 때 Left-Left 회전, 52를 삽입할 때 Right-Right 회전이 발생한 것을 확인할 수 있습니다.
1.Insert Element into the tree 2.show Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 13 ... Enter your Choice: 1 Enter value to be inserted: 4 Left-Left Rotation ... Enter your Choice: 1 Enter value to be inserted: 52 Right-Right Rotation ... Enter your Choice: 3 Inorder Traversal: 4 5 8 10 11 13 15 16 Enter your Choice: 4 Preorder Traversal: 10 5 4 8 13 11 15 16 Enter your Choice: 5 Postorder Traversal: 4 8 5 11 16 15 13 10 ... Enter your Choice: 6
정리
이 예제는 AVL 트리의 핵심 개념인 균형 인수 계산과 네 가지 회전(LL, LR, RR, RL)을 모두 포함하고 있습니다. 삽입 시마다 balance() 함수가 호출되어 트리의 높이 차이를 검사하고, 필요한 경우 적절한 회전을 통해 균형을 복원합니다. 중위 순회 결과가 항상 오름차순으로 정렬되어 출력되는 점에서, 회연 후에도 이진 탐색 트리의 정렬 속성이 그대로 보존된다는 사실도 확인할 수 있습니다.