이진 탐색 트리(Binary Search Tree, BST)는 효율적인 데이터 검색과 관리를 위해 설계된 특수한 형태의 트리 자료구조입니다. BST는 다음과 같은 규칙을 따릅니다.
- 왼쪽 자식 노드의 값은 항상 부모 노드의 값보다 작습니다.
- 오른쪽 자식 노드의 값은 항상 부모 노드의 값보다 큽니다.
- 모든 노드는 각각 하나의 이진 탐색 트리를 이룹니다.
이러한 규칙 덕분에 BST는 탐색(search), 최솟값·최댓값 찾기 같은 연산의 시간 복잡도를 크게 줄일 수 있습니다.
이진 탐색 트리의 삭제(Delete) 연산
삭제 연산은 트리에서 지정된 노드를 제거하는 작업입니다. 삭제하려는 노드의 구조에 따라 다음 세 가지 경우로 나눌 수 있습니다.
1. 리프 노드(자식이 없는 노드) 삭제
가장 간단한 경우입니다. 리프 노드는 자식이 없으므로 해당 노드만 제거하면 되고, 트리의 나머지 구조에는 영향을 주지 않습니다.
예를 들어 아래 트리에서 리프 노드 7을 삭제하면, 노드 7만 사라지고 나머지 트리는 그대로 유지됩니다.
2. 자식이 하나인 노드 삭제
삭제할 노드에 자식이 하나만 있는 경우, 해당 자식 노드를 삭제 대상 노드의 위치로 올려 대체한 뒤 원래 노드를 제거합니다.
예를 들어 BST에서 노드 2를 삭제하면, 노드 2의 자식이 노드 2의 부모와 직접 연결되어 트리의 규칙이 유지됩니다.
3. 자식이 두 개인 노드 삭제
삭제할 노드에 자식이 두 개 있는 경우가 가장 복잡합니다. 이때는 중위 순회(inorder traversal) 순서를 활용합니다. 삭제할 노드를 제거한 뒤, 그 자리를 중위 순회 기준의 인접 노드(보통 오른쪽 서브트리에서 가장 작은 값, 즉 후계자(successor))로 대체하고 나머지 노드들을 재배치합니다.
예를 들어 BST에서 노드 5를 삭제하면, 오른쪽 서브트리의 최솟값이 그 자리를 대신하게 됩니다.
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 inordertraversal(struct node *root){
if (root != NULL){
inordertraversal(root->left);
printf("%d ", root->key);
inordertraversal(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
node->right = insert(node->right, key);
return node;
}
struct node * minValueNode(struct node* node){
struct node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node* deleteNode(struct node* root, int key){
if (root == NULL) return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else{
if (root->left == NULL){
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL){
struct node *temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
int main(){
struct node *root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
printf("Inorder traversal of the given tree \n");
inordertraversal(root);
printf("\nDelete 20\n");
root = deleteNode(root, 20);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
printf("\nDelete 30\n");
root = deleteNode(root, 30);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
printf("\nDelete 50\n");
root = deleteNode(root, 50);
printf("Inorder traversal of the modified tree \n");
inordertraversal(root);
return 0;
}실행 결과
Inorder traversal of the given tree 20 30 40 50 60 70 80 Delete 20 Inorder traversal of the modified tree 30 40 50 60 70 80 Delete 30 Inorder traversal of the modified tree 40 50 60 70 80 Delete 50 Inorder traversal of the modified tree 40 60 70 80
실행 결과를 보면, 노드 20(리프 노드)은 단순히 제거되고, 노드 30(자식이 하나)은 자식이 위치를 대체하며, 노드 50(자식이 둘)은 오른쪽 서브트리의 최솟값인 60이 그 자리를 대신하는 것을 확인할 수 있습니다.