AVL 트리는 자가 균형 이진 탐색 트리(Self-balancing Binary Search Tree)의 한 종류로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 항상 1 이하를 유지하도록 설계된 자료구조입니다. 이 균형 조건 덕분에 삽입·삭제·탐색 연산이 항상 O(log n)의 시간 복잡도를 보장받을 수 있습니다.
AVL 트리의 동작 원리
노드가 삽입되거나 삭제될 때 트리의 균형이 깨질 수 있습니다. 이때 AVL 트리는 각 노드의 균형인수(Balance Factor), 즉 왼쪽 서브트리 높이에서 오른쪽 서브트리 높이를 뺀 값을 계산하고, 그 값이 1보다 크거나 -1보다 작으면 회전(Rotation) 연산을 통해 트리를 재조정합니다.
회전은 불균형이 발생한 패턴에 따라 네 가지 방식으로 수행됩니다.
- LL 회전(Left-Left): 왼쪽-왼쪽으로 불균형이 발생한 경우 단순 우회전
- RR 회전(Right-Right): 오른쪽-오른쪽으로 불균형이 발생한 경우 단순 좌회전
- LR 회전(Left-Right): 왼쪽-오른쪽으로 불균형이 발생한 경우 이중 회전
- RL 회전(Right-Left): 오른쪽-왼쪽으로 불균형이 발생한 경우 이중 회전
알고리즘 개요
시작
avl_tree 클래스에 다음 함수들을 선언한다:
balance() = 균형인수를 계산하여 트리의 균형을 맞춘다.
그 값을 bal_factor에 저장한다.
bal_factor > 1이면 왼쪽 서브트리의 균형을 잡는다.
bal_factor < -1이면 오른쪽 서브트리의 균형을 잡는다.
insert() = 트리에 원소를 삽입한다.
트리가 비어 있으면 데이터를 루트로 삽입한다.
트리가 비어 있지 않고 데이터 < 루트 값이면
데이터를 왼쪽 자식으로 삽입한다.
그렇지 않으면
데이터를 오른쪽 자식으로 삽입한다.
끝.예제 코드
#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)//switch 문 실행
{
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;
}실행 결과
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 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: 10 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: 15 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: 5 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: 11 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: 4 Left-Left Rotation1.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: 8 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: 16 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: 3 Inorder Traversal: 4 5 8 10 11 13 15 16 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: 4 Preorder Traversal: 10 5 4 8 13 11 15 16 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: 5 Postorder Traversal: 4 8 5 11 16 15 13 10 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: 14 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: 3 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: 7 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: 9 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: 52 Right-Right Rotation 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: 6
결과 분석
실행 결과를 보면, 값 4를 삽입하는 시점에 왼쪽 서브트리의 높이가 초과되어 Left-Left Rotation이 자동으로 수행되었고, 값 52를 삽입할 때에는 오른쪽으로 불균형이 생겨 Right-Right Rotation이 수행된 것을 확인할 수 있습니다. 또한 중위 순회 결과가 4 5 8 10 11 13 15 16처럼 항상 오름차순으로 출력되므로, 회전 후에도 이진 탐색 트리의 정렬 속성이 올바르게 유지되었음을 알 수 있습니다. 전위 순회 결과의 루트 값인 10을 보면 트리가 균형 있게 재구성되었음을 확인할 수 있습니다.