이진 탐색 트리(Binary Search Tree, BST)는 모든 노드가 다음 조건을 만족하는 정렬된 이진 트리입니다.
- 노드의 오른쪽 서브트리에 있는 키는 항상 부모 노드의 키보다 큽니다.
- 노드의 왼쪽 서브트리에 있는 키는 부모 노드의 키보다 작거나 같습니다.
- 각 노드는 최대 두 개의 자식 노드만 가질 수 있습니다.
트리 회전(Tree Rotation)이란?
트리 회전은 이진 트리에서 요소들의 순서(정렬 속성)를 그대로 유지하면서 트리의 구조만 변경하는 연산입니다. 회전이 일어나면 한 노드는 위로 올라가고 다른 노드는 아래로 내려갑니다.
회전은 작은 서브트리는 아래로, 큰 서브트리는 위로 이동시켜 트리의 높이를 줄이는 데 사용되며, 이를 통해 탐색·삽입·삭제 등 대부분의 트리 연산 성능이 향상됩니다. 회전 방향은 노드가 이동하는 쪽에 따라 결정되며, 어떤 자식이 루트 자리를 차지하느냐로 설명하기도 합니다.
이 글에서 소개하는 코드는 단순한 오른쪽 회전뿐 아니라 AVL 트리의 균형 인수(Balance Factor)를 계산하여 LL(왼쪽-왼쪽), RR(오른쪽-오른쪽), LR(왼쪽-오른쪽), RL(오른쪽-왼쪽) 네 가지 회전을 모두 수행하는 완전한 구현 예제입니다.
알고리즘
시작
구조체 avl을 생성하여 데이터 d, 왼쪽 포인터 l, 오른쪽 포인터 r 변수를 선언한다.
클래스 avl_tree를 선언하고 다음 함수들을 정의한다.
height() - max 함수를 이용해 트리의 높이를 계산한다.
difference() - 왼쪽과 오른쪽 서브트리의 높이 차이를 계산한다.
rr_rotat() - 오른쪽-오른쪽(RR) 회전을 수행한다.
ll_rotat() - 왼쪽-왼쪽(LL) 회전을 수행한다.
lr_rotat() - 왼쪽-오른쪽(LR) 회전을 수행한다.
rl_rotat() - 오른쪽-왼쪽(RL) 회전을 수행한다.
balance() - 균형 인수를 구해 트리의 균형을 맞춘다.
bal_factor > 1이면 왼쪽 서브트리를,
bal_factor < -1이면 오른쪽 서브트리를 균형화한다.
insert() - 트리에 요소를 삽입한다.
show() - 트리 구조를 출력한다.
inorder() - 중위 순회 결과를 출력한다.
preorder() - 전위 순회 결과를 출력한다.
postorder() - 후위 순회 결과를 출력한다.
main()에서 switch 문으로 사용자 선택에 따라 각 함수를 호출한다.
종료.예제 코드
#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;
}실행 결과
프로그램을 실행하면 메뉴 기반으로 동작하며, 값들을 삽입하는 과정에서 균형 인수가 임계값을 벗어날 때마다 회전이 자동으로 수행됩니다. 아래는 주요 실행 흐름을 정리한 결과입니다.
메뉴: 1.삽입 / 2.AVL 트리 출력 / 3.중위 순회 / 4.전위 순회 / 5.후위 순회 / 6.종료 값 삽입: 13 → 10 → 15 → 5 → 11 → 4 → 4 삽입 시 균형 인수 초과로 "Left-Left Rotation" 발생 값 삽입: 8 → 16 후 중위 순회 선택: Inorder Traversal: 4 5 8 10 11 13 15 16 전위 순회 선택: Preorder Traversal: 10 5 4 8 13 11 15 16 후위 순회 선택: Postorder Traversal: 4 8 5 11 16 15 13 10 값 삽입: 14 → 3 → 7 → 9 → 52 → 52 삽입 시 "Right-Right Rotation" 발생 6번 선택 시 프로그램 종료
정리
이 프로그램은 이진 탐색 트리의 삽입 과정에서 발생할 수 있는 편향 문제를 AVL 트리의 회전 연산으로 해결하는 방법을 보여줍니다. 특히 값 4와 52를 삽입할 때 각각 Left-Left 회전과 Right-Right 회전이 실행되어 트리의 균형이 자동으로 유지되는 것을 확인할 수 있습니다. 중위 순회 결과가 항상 오름차순으로 출력되므로, 회연 후에도 BST의 정렬 속성이 그대로 보존됨을 알 수 있습니다.