이진 검색 트리(Binary Search Tree, BST)는 모든 노드가 정렬된 순서를 유지하는 이진 트리 자료구조입니다. BST는 다음과 같은 핵심 속성을 만족해야 합니다.
- 노드의 오른쪽 서브트리에 있는 모든 키는 부모 노드의 키보다 크거나 같습니다.
- 노드의 왼쪽 서브트리에 있는 모든 키는 부모 노드의 키보다 작습니다.
- 각 노드는 최대 두 개의 자식 노드만 가질 수 있습니다.
이러한 구조 덕분에 BST에서는 검색, 삽입, 삭제 연산을 평균적으로 O(log n)의 시간 복잡도로 수행할 수 있습니다. 아래에서는 C++로 이진 검색 트리를 구현하는 방법을 단계별로 살펴보겠습니다.
알고리즘 설계
BST 클래스에는 다음과 같은 주요 함수들이 포함됩니다.
- search(): 트리에서 특정 항목을 검색합니다. 루트부터 시작해 값을 비교하며 왼쪽 또는 오른쪽으로 이동하고, 찾은 경우 해당 깊이(depth)를 출력합니다.
- insert(): 트리에 새 항목을 삽입합니다. 트리가 비어 있으면 데이터를 루트로 설정하고, 그렇지 않으면 값의 크기를 비교해 왼쪽 또는 오른쪽 자식으로 재귀적으로 삽입합니다.
- del(): 트리에서 항목을 삭제하며, 삭제 대상 노드의 자식 상태에 따라 네 가지 경우(casea, caseb, casec)로 나뉩니다.
- casea(): 자식이 없는 리프 노드(왼쪽 = NULL, 오른쪽 = NULL)인 경우 호출됩니다.
- caseb(): 자식이 하나만 있는 경우(왼쪽만 존재 또는 오른쪽만 존재) 호출됩니다.
- casec(): 자식이 둘 다 있는 경우 호출되며, 오른쪽 서브트리의 최솟값(중위 후속자, inorder successor)으로 대체합니다.
- inorder(): 중위 순회 — 왼쪽 → 루트 → 오른쪽 순서로 노드를 방문합니다. 정렬된 결과를 얻을 수 있습니다.
- preorder(): 전위 순회 — 루트 → 왼쪽 → 오른쪽 순서로 노드를 방문합니다.
- postorder(): 후위 순회 — 왼쪽 → 오른쪽 → 루트 순서로 노드를 방문합니다.
- show(): 트리의 구조를 시각적으로 출력합니다.
C++ 예제 코드
#include <iostream>
#include <cstdlib>
using namespace std;
// 노드 선언
struct nod {
int info;
struct nod *l;
struct nod *r;
}*r;
class BST {
public:
// 함수 선언
void search(nod *, int);
void find(int, nod **, nod **);
void insert(nod *, nod *);
void del(int);
void casea(nod *, nod *);
void caseb(nod *, nod *);
void casec(nod *, nod *);
void preorder(nod *);
void inorder(nod *);
void postorder(nod *);
void show(nod *, int);
BST() {
r = NULL;
}
};
// 요소의 위치 찾기
void BST::find(int i, nod **par, nod **loc) {
nod *ptr, *ptrsave;
if (r == NULL) {
*loc = NULL;
*par = NULL;
return;
}
if (i == r->info) {
*loc = r;
*par = NULL;
return;
}
if (i < r->info)
ptr = r->l;
else
ptr = r->r;
ptrsave = r;
while (ptr != NULL) {
if (i == ptr->info) {
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (i < ptr->info)
ptr = ptr->l;
else
ptr = ptr->r;
}
*loc = NULL;
*par = ptrsave;
}
// 요소 검색
void BST::search(nod *root, int data) {
int depth = 0;
nod *temp = root;
while (temp != NULL) {
depth++;
if (temp->info == data) {
cout << "\n데이터를 깊이 " << depth << "에서 찾았습니다" << endl;
return;
} else if (temp->info > data)
temp = temp->l;
else
temp = temp->r;
}
cout << "\n데이터를 찾을 수 없습니다" << endl;
return;
}
// 요소 삽입
void BST::insert(nod *tree, nod *newnode) {
if (r == NULL) {
r = new nod;
r->info = newnode->info;
r->l = NULL;
r->r = NULL;
cout << "루트 노드가 추가되었습니다" << endl;
return;
}
if (tree->info == newnode->info) {
cout << "이미 트리에 존재하는 요소입니다" << endl;
return;
}
if (tree->info > newnode->info) {
if (tree->l != NULL) {
insert(tree->l, newnode);
} else {
tree->l = newnode;
(tree->l)->l = NULL;
(tree->l)->r = NULL;
cout << "노드가 왼쪽에 추가되었습니다" << endl;
return;
}
} else {
if (tree->r != NULL) {
insert(tree->r, newnode);
} else {
tree->r = newnode;
(tree->r)->l = NULL;
(tree->r)->r = NULL;
cout << "노드가 오른쪽에 추가되었습니다" << endl;
return;
}
}
}
// 요소 삭제
void BST::del(int i) {
nod *par, *loc;
if (r == NULL) {
cout << "트리가 비어 있습니다" << endl;
return;
}
find(i, &par, &loc);
if (loc == NULL) {
cout << "트리에 해당 항목이 없습니다" << endl;
return;
}
if (loc->l == NULL && loc->r == NULL) {
casea(par, loc);
cout << "항목이 삭제되었습니다" << endl;
}
if (loc->l != NULL && loc->r == NULL) {
caseb(par, loc);
cout << "항목이 삭제되었습니다" << endl;
}
if (loc->l == NULL && loc->r != NULL) {
caseb(par, loc);
cout << "항목이 삭제되었습니다" << endl;
}
if (loc->l != NULL && loc->r != NULL) {
casec(par, loc);
cout << "항목이 삭제되었습니다" << endl;
}
free(loc);
}
// 자식이 없는 경우
void BST::casea(nod *par, nod *loc) {
if (par == NULL) {
r = NULL;
} else {
if (loc == par->l)
par->l = NULL;
else
par->r = NULL;
}
}
// 자식이 하나인 경우
void BST::caseb(nod *par, nod *loc) {
nod *child;
if (loc->l != NULL)
child = loc->l;
else
child = loc->r;
if (par == NULL) {
r = child;
} else {
if (loc == par->l)
par->l = child;
else
par->r = child;
}
}
// 자식이 둘인 경우
void BST::casec(nod *par, nod *loc) {
nod *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->r;
while (ptr->l != NULL) {
ptrsave = ptr;
ptr = ptr->l;
}
suc = ptr;
parsuc = ptrsave;
if (suc->l == NULL && suc->r == NULL)
casea(parsuc, suc);
else
caseb(parsuc, suc);
if (par == NULL) {
r = suc;
} else {
if (loc == par->l)
par->l = suc;
else
par->r = suc;
}
suc->l = loc->l;
suc->r = loc->r;
}
// 전위 순회
void BST::preorder(nod *ptr) {
if (r == NULL) {
cout << "트리가 비어 있습니다" << endl;
return;
}
if (ptr != NULL) {
cout << ptr->info << " ";
preorder(ptr->l);
preorder(ptr->r);
}
}
// 중위 순회
void BST::inorder(nod *ptr) {
if (r == NULL) {
cout << "트리가 비어 있습니다" << endl;
return;
}
if (ptr != NULL) {
inorder(ptr->l);
cout << ptr->info << " ";
inorder(ptr->r);
}
}
// 후위 순회
void BST::postorder(nod *ptr) {
if (r == NULL) {
cout << "트리가 비어 있습니다" << endl;
return;
}
if (ptr != NULL) {
postorder(ptr->l);
postorder(ptr->r);
cout << ptr->info << " ";
}
}
// 트리 구조 출력
void BST::show(nod *ptr, int level) {
int i;
if (ptr != NULL) {
show(ptr->r, level + 1);
cout << endl;
if (ptr == r)
cout << "루트->: ";
else {
for (i = 0; i < level; i++)
cout << " ";
}
cout << ptr->info;
show(ptr->l, level + 1);
}
}
int main() {
int c, n, item;
BST bst;
nod *t;
while (1) {
cout << "1.요소 삽입" << endl;
cout << "2.요소 삭제" << endl;
cout << "3.요소 검색" << endl;
cout << "4.중위 순회" << endl;
cout << "5.전위 순회" << endl;
cout << "6.후위 순회" << endl;
cout << "7.트리 출력" << endl;
cout << "8.종료" << endl;
cout << "선택하세요 : ";
cin >> c;
switch (c) { // 스위치 연산 수행
case 1:
t = new nod;
cout << "삽입할 숫자 입력 : ";
cin >> t->info;
bst.insert(r, t);
break;
case 2:
if (r == NULL) {
cout << "트리가 비어 있어 삭제할 것이 없습니다" << endl;
continue;
}
cout << "삭제할 숫자 입력 : ";
cin >> n;
bst.del(n);
break;
case 3:
cout << "검색:" << endl;
cin >> item;
bst.search(r, item);
break;
case 4:
cout << "BST 중위 순회 결과:" << endl;
bst.inorder(r);
cout << endl;
break;
case 5:
cout << "BST 전위 순회 결과:" << endl;
bst.preorder(r);
cout << endl;
break;
case 6:
cout << "BST 후위 순회 결과:" << endl;
bst.postorder(r);
cout << endl;
break;
case 7:
cout << "BST 출력:" << endl;
bst.show(r, 1);
cout << endl;
break;
case 8:
exit(1);
default:
cout << "잘못된 선택입니다" << endl;
}
}
}실행 결과 예시
프로그램을 실행하면 메뉴 기반 인터페이스가 나타나며, 사용자가 선택한 번호에 따라 각 연산이 수행됩니다.
1.요소 삽입 2.요소 삭제 3.요소 검색 4.중위 순회 5.전위 순회 6.후위 순회 7.트리 출력 8.종료 선택하세요 : 1 삽입할 숫자 입력 : 6 루트 노드가 추가되었습니다 선택하세요 : 1 삽입할 숫자 입력 : 7 노드가 오른쪽에 추가되었습니다 선택하세요 : 1 삽입할 숫자 입력 : 5 노드가 왼쪽에 추가되었습니다 선택하세요 : 3 검색: 7 데이터를 깊이 2에서 찾았습니다 선택하세요 : 4 BST 중위 순회 결과: 4 5 6 7 선택하세요 : 5 BST 전위 순회 결과: 6 5 4 7 선택하세요 : 6 BST 후위 순회 결과: 4 5 7 6 선택하세요 : 7 BST 출력: 7 루트->: 6 5 4 선택하세요 : 2 삭제할 숫자 입력 : 5 항목이 삭제되었습니다 선택하세요 : 8
핵심 포인트 정리
- 중위 순회를 수행하면 트리의 모든 값이 오름차순으로 정렬되어 출력됩니다. 위 예시에서 4 5 6 7이 출력된 것을 확인할 수 있습니다.
- 검색 연산은 루트에서 시작해 매 단계마다 탐색 범위가 절반으로 줄어들므로, 균형 잡힌 트리에서는 매우 효율적입니다.
- 삭제 연산은 대상 노드의 자식 개수에 따라 세 가지 경우로 처리되며, 자식이 둘인 경우에는 오른쪽 서브트리의 최솟값(중위 후속자)이 그 자리를 대신합니다.
- 실제 프로젝트에서는 메모리 누수를 방지하기 위해
free()대신 스마트 포인터나 소멸자를 활용한 메모리 관리를 권장합니다.