이진 탐색 트리(BST)란 무엇인가?
이진 탐색 트리(Binary Search Tree, BST)는 데이터를 효율적으로 저장하고 탐색하기 위해 고안된 특수한 형태의 이진 트리입니다. BST는 반드시 다음 세 가지 규칙을 따릅니다.
- 왼쪽 자식 노드의 값은 항상 부모 노드의 값보다 작습니다.
- 오른쪽 자식 노드의 값은 항상 부모 노드의 값보다 큽니다.
- 모든 노드는 각각 독립적으로 하나의 이진 탐색 트리를 이룹니다(재귀적 구조).
예를 들어 루트가 23인 BST에 15, 12, 17, 32, 29, 45를 차례로 삽입하면, 중위 순회(in-order traversal) 시 12 → 15 → 17 → 23 → 29 → 32 → 45 순서로 정렬된 값이 출력됩니다.
이러한 구조적 특성 덕분에 BST는 단순 배열의 선형 탐색(O(n))보다 훨씬 빠르게 검색, 최솟값·최댓값 찾기 등의 연산을 수행할 수 있습니다. 균형이 잘 유지되는 경우 평균 시간 복잡도는 O(log n)입니다.
BST에서의 검색(Search) 연산
이진 탐색 트리에서 특정 키(key)를 찾는 과정은 다음과 같습니다.
- 찾으려는 키를 트리의 루트 노드와 비교합니다.
- 키가 루트 노드의 값과 같다면 → 원소를 찾은 것이므로 검색을 종료합니다.
- 키가 루트 노드보다 크면 → 오른쪽 서브트리로 이동해 검색을 계속합니다.
- 키가 루트 노드보다 작으면 → 왼쪽 서브트리로 이동해 검색을 계속합니다.
비교할 때마다 탐색 대상 범위가 절반으로 줄어들기 때문에, 균형 잡힌 트리에서는 매우 적은 비교 횟수만으로 원하는 값을 찾을 수 있습니다.
검색 연산 C++ 코드 예제
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
struct node* search(struct node* root, int key){
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int main(){
struct node *root = NULL;
root = insert(root, 23);
insert(root, 15);
insert(root, 12);
insert(root, 17);
insert(root, 32);
insert(root, 29);
insert(root, 45);
printf("The tree is :\n");
traversetree(root);
printf("\nSearching for 12 in this tree ");
if(search(root, 12))
printf("\nelement found");
else
printf("\nelement not found");
return 0;
}
실행 결과
The tree is : 12 15 17 23 29 32 45 Searching for 12 in this tree element found
BST에서의 삽입(Insertion) 연산
BST에서 새로운 노드는 항상 리프(leaf) 노드 자리에 추가됩니다. 삽입 절차는 다음과 같습니다.
- 루트 노드부터 시작해 새 키와 현재 노드의 값을 비교합니다.
- 새 키가 더 작으면 왼쪽으로, 더 크면 오른쪽으로 이동합니다.
- 더 이상 내려갈 곳이 없는 빈 자리(NULL)에 도달하면 그곳에 새 노드를 배치합니다.
예를 들어 루트가 5이고 오른쪽으로 8, 10이 이어진 BST에 값 12를 삽입하는 과정을 살펴보겠습니다.
- 12를 루트 노드 5와 비교 → 12 > 5이므로 오른쪽 서브트리로 이동합니다.
- 오른쪽 자식 노드 8과 비교 → 12 > 8이므로 오른쪽 자식의 오른쪽으로 이동합니다.
- 노드 10과 비교 → 12 > 10이므로 이 노드의 오른쪽 자리에 배치합니다.
이렇게 해서 12가 리프 노드로 추가된 새로운 트리가 완성됩니다.
삽입 연산 C++ 코드 예제
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int main(){
struct node *root = NULL;
root = insert(root, 23);
insert(root, 15);
insert(root, 12);
insert(root, 17);
insert(root, 32);
insert(root, 29);
printf("The tree is :\n");
traversetree(root);
printf("\nInserting 45 to the tree\n");
insert(root, 45);
printf("Tree after insertion is :\n");
traversetree(root);
return 0;
}
실행 결과
The tree is : 12 15 17 23 29 32 Inserting 45 to the tree Tree after insertion is : 12 15 17 23 29 32 45
마무리: 시간 복잡도 정리
BST의 검색과 삽입 연산 성능은 트리의 균형 상태에 따라 달라집니다.
- 평균(균형 트리): O(log n)
- 최악(편향 트리): O(n) — 노드가 한쪽 방향으로만 치우친 경우
따라서 실무에서는 AVL 트리나 레드-블랙 트리처럼 스스로 균형을 유지하는 자가 균형(self-balancing) BST를 활용하면, 어떤 입력 순서가 들어와도 항상 O(log n) 수준의 안정적인 성능을 보장받을 수 있습니다.