이진 탐색 트리(Binary Search Tree)란?
이진 탐색 트리(BST)는 정렬된 이진 트리로, 모든 노드는 다음 두 가지 성질을 만족해야 합니다.
- 노드의 오른쪽 서브트리에는 부모 노드의 키보다 큰 값들만 존재합니다.
- 노드의 왼쪽 서브트리에는 부모 노드의 키보다 작은 값들만 존재하며, 각 노드는 자식을 최대 두 개까지만 가질 수 있습니다.
이러한 구조 덕분에 탐색, 삽입, 삭제 연산을 평균 O(log n) 시간에 수행할 수 있습니다.
트리 회전(Tree Rotation)이란?
트리 회전은 트리 내 요소들의 순서(정렬 속성)를 해치지 않으면서 트리의 구조를 변경하는 연산입니다. 특정 노드 하나를 위로 올리고 다른 노드 하나를 아래로 내리는 방식으로 동작합니다.
회전은 트리의 형태를 바꾸고, 작은 서브트리는 아래로, 큰 서브트리는 위로 이동시켜 트리의 높이를 줄여줍니다. 그 결과 탐색, 삽입, 삭제 등 대부분의 트리 연산 성능이 향상됩니다. 회전 방향은 노드가 이동하는 쪽을 기준으로 정의되기도 하고, 어떤 자식이 루트 자리를 대신하느냐에 따라 정의되기도 합니다.
아래에서 소개할 C++ 프로그램은 자가 균형 이진 탐색 트리인 AVL 트리를 기반으로 왼쪽 회전(Left Rotation)과 오른쪽 회전(Right Rotation)을 포함한 네 가지 회전(LL, RR, LR, RL)을 모두 구현한 예제입니다.
주요 함수 설명
높이 및 균형 계산
height(avl *) : 인수로 받은 AVL 트리의 높이를 계산해 반환합니다.
difference(avl *) : 주어진 노드의 왼쪽 서브트리와 오른쪽 서브트리 높이의 차이, 즉 균형 인수(balance factor)를 계산합니다.
네 가지 회전 함수
avl *rr_rotat(avl *) : 오른쪽-오른쪽(RR) 상황에서 사용하는 회전으로, 오른쪽 자식을 위로 끌어올리는 단일 왼쪽 회전을 수행합니다.
avl *ll_rotat(avl *) : 왼쪽-왼쪽(LL) 상황에서 사용하는 회전으로, 왼쪽 자식을 위로 끌어올리는 단일 오른쪽 회전을 수행합니다.
avl *lr_rotat(avl*) : 왼쪽-오른쪽(LR) 상황에서 사용하는 회전으로, 왼쪽 회전 후 오른쪽 회전을 연달아 적용하는 이중 회전입니다.
avl *rl_rotat(avl *) : 오른쪽-왼쪽(RL) 상황에서 사용하는 회전으로, 오른쪽 회전 후 왼쪽 회전을 연달아 적용하는 이중 회전입니다.
삽입과 순회
avl * balance(avl *) : 균형 인수를 계산해 트리 전체의 균형을 맞추는 연산을 수행합니다.
avl * insert(avl*, int) : 새로운 값을 트리에 삽입하고, 삽입 경로상의 노드들을 재귀적으로 균형화합니다.
show(avl*, int) : 트리의 구조를 들여쓰기 형태로 화면에 출력합니다.
inorder(avl *) : 중위 순회(in-order) 방식으로 트리를 탐색합니다. 정렬된 순서로 값이 출력됩니다.
preorder(avl *) : 전위 순회(pre-order) 방식으로 트리를 탐색합니다.
postorder(avl*) : 후위 순회(post-order) 방식으로 트리를 탐색합니다.
C++ 전체 소스 코드
아래 코드는 메뉴 기반으로 동작하며, 값 삽입 시마다 필요한 경우 자동으로 회전을 수행해 트리의 균형을 유지합니다.
#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;
}실행 결과
프로그램을 실행하면 메뉴가 반복해서 표시됩니다. 여러 값을 삽입하다 보면 균형이 깨지는 시점에 Left-Left Rotation, 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: 1 Enter value to be inserted: 13 ...(중략)... Enter your Choice: 1 Enter value to be inserted: 4 Left-Left 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: 1 Enter value to be inserted: 52 Right-Right Rotation ... Enter your Choice: 6
정리
AVL 트리는 삽입·삭제가 일어날 때마다 균형 인수를 검사하고, 필요 시 LL, RR, LR, RL 네 가지 회전을 통해 트리 높이를 O(log n)으로 유지합니다. 이번 예제처럼 회전 로직을 직접 구현해 보면 이진 탐색 트리가 스스로 균형을 잡는 원리를 명확하게 이해할 수 있습니다. 특히 중위 순회 결과가 항상 정렬된 값으로 출력되는 점을 확인하면, 회전 연산이 트리의 정렬 속성을 전혀 훼손하지 않는다는 사실도 함께 알 수 있습니다.