이진 탐색 트리(Binary Search Tree, BST)는 데이터를 효율적으로 저장하고 검색하기 위해 특정 규칙을 갖는 이진 트리입니다. 일반적인 이진 트리와 달리, 노드의 배치에 엄격한 순서 규칙이 적용되기 때문에 탐색·삽입·삭제 작업을 빠르게 수행할 수 있습니다.
이진 탐색 트리의 성질
이진 탐색 트리는 다음과 같은 조건을 만족해야 합니다.
- 모든 이진 탐색 트리는 이진 트리이다.
- 왼쪽 자식 노드는 항상 부모(루트) 노드보다 작은 값을 가진다.
- 오른쪽 자식 노드는 항상 부모(루트) 노드보다 큰 값을 가진다.
- 이상적인 이진 탐색 트리에서는 같은 값이 중복되어 저장되지 않는다.
중위 순회(Inorder Traversal)로 확인하기
이러한 성질을 만족하는 트리를 중위 순회(왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서)로 탐색하면, 노드들이 항상 오름차순으로 정렬된 결과를 얻게 됩니다. 예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.
위 트리는 앞서 언급한 모든 성질을 만족하는 이진 탐색 트리입니다. 이 트리를 중위 순회하면 5, 8, 10, 15, 16, 20, 23이라는 정렬된 결과가 출력됩니다. 이것이 바로 이진 탐색 트리의 핵심 특징입니다.
C++로 구현하는 이진 탐색 트리
아래 코드는 노드 생성, 삽입, 중위 순회 기능을 포함한 간단한 이진 탐색 트리의 C++ 구현 예제입니다.
예제 코드
#include<iostream>
using namespace std;
class node{
public:
int h_left, h_right, bf, value;
node *left, *right;
};
class tree{
private:
node *get_node(int key);
public:
node *root;
tree(){
root = NULL; // 처음에는 루트를 NULL로 설정
}
void inorder_traversal(node *r);
node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
node *new_node;
new_node = new node; // 새 노드를 동적으로 생성
new_node->h_left = 0; new_node->h_right = 0;
new_node->bf = 0;
new_node->value = key; // 주어진 키 값을 저장
new_node->left = NULL; new_node->right = NULL;
return new_node;
}
void tree::inorder_traversal(node *r){
if(r != NULL){ // 루트가 존재하면 왼쪽 - 루트 - 오른쪽 순으로 방문
inorder_traversal(r->left);
cout << r->value << " ";
inorder_traversal(r->right);
}
}
node *tree::insert_node(node *root, int key){
if(root == NULL){
return (get_node(key)); // 트리가 비어 있으면 새 노드를 루트로 생성
}
if(key < root->value){ // 키가 루트 값보다 작으면 왼쪽으로 이동
root->left = insert_node(root->left, key);
}else if(key > root->value){ // 키가 루트 값보다 크면 오른쪽으로 이동
root->right = insert_node(root->right, key);
}
return root; // 키가 이미 존재하면 다시 삽입하지 않음
}
main(){
node *root;
tree my_tree;
// 트리에 여러 키를 삽입
my_tree.root = my_tree.insert_node(my_tree.root, 10);
my_tree.root = my_tree.insert_node(my_tree.root, 5);
my_tree.root = my_tree.insert_node(my_tree.root, 16);
my_tree.root = my_tree.insert_node(my_tree.root, 20);
my_tree.root = my_tree.insert_node(my_tree.root, 15);
my_tree.root = my_tree.insert_node(my_tree.root, 8);
my_tree.root = my_tree.insert_node(my_tree.root, 23);
cout << "In-Order Traversal: ";
my_tree.inorder_traversal(my_tree.root);
}실행 결과
In-Order Traversal: 5 8 10 15 16 20 23
코드 동작 원리 정리
- 노드 삽입: 삽입할 키가 현재 노드보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 재귀적으로 이동하여 적절한 위치에 배치합니다.
- 중복 처리: 이미 존재하는 키는 삽입하지 않고 그대로 반환합니다.
- 중위 순회: 재귀 호출을 통해 왼쪽 → 루트 → 오른쪽 순서로 방문하므로 항상 정렬된 출력을 얻습니다.
이처럼 이진 탐색 트리는 단순한 구조만으로도 데이터를 체계적으로 관리할 수 있으며, 균형 잡힌 경우 탐색 시간 복잡도는 O(log n)으로 매우 효율적입니다. 실무에서는 AVL 트리나 레드-블랙 트리 같은 자가 균형 이진 탐색 트리가 널리 활용됩니다.