이진 탐색 트리(Binary Search Tree, BST)는 프로그래밍에서 가장 중요한 자료구조 중 하나입니다. 효율적인 데이터 검색, 삽입, 삭제를 가능하게 하며 다양한 알고리즘과 시스템에서 사용됩니다.
(1) 이진 탐색 트리란?
이진 탐색 트리는 **이진 트리(Binary Tree)**의 한 종류로, 데이터를 정렬된 상태로 저장하며 효율적인 검색과 관리가 가능하도록 설계된 자료구조입니다.
(2) 기본 원리
- 각 노드는 최대 두 개의 자식을 가집니다.
- 왼쪽 서브트리에는 부모 노드보다 작거나 같은 값이 저장됩니다.
- 오른쪽 서브트리에는 부모 노드보다 큰 값이 저장됩니다.
(3) 이진 탐색 트리의 특징
- 정렬된 데이터 구조: 노드를 중위 순회(Inorder Traversal)하면 정렬된 데이터가 출력됩니다.
- 효율적인 연산: 검색, 삽입, 삭제가 트리 높이에 비례하는 시간 복잡도 O(log n)로 동작합니다.
(4) 이진 탐색 트리의 구조와 동작
삽입(Insert)
새로운 데이터를 추가할 때, 부모 노드와 값을 비교하며 적절한 위치를 찾아 삽입합니다. 삽입 후 항상 “부모노드보다 작거나 같은 자식 노드는 부모노드 왼쪽에 존재”하고, “부모노드보다 큰 자식 노드는 부모노드 오른쪽에 존재”한다는 규칙을 항상 만족합니다.
검색(Search)
특정 데이터를 찾기 위해 루트에서 시작하여 값을 비교하며 트리를 내려갑니다. 현재 노드보다 찾는 값이 작은경우 왼쪽으로, 현재 노드보다 찾는 값이 큰 경우 오른쪽으로 내려갑니다.
삭제(Delete)
노드를 삭제할 때, 다음 세 가지 경우를 고려합니다:
- 자식이 없는 노드: 단순히 제거.
- 자식이 하나인 노드: 자식을 부모와 연결.
- 자식이 둘인 노드: 오른쪽 서브트리의 최소값을 찾아 교체 후 삭제.
(5) 이진 탐색 트리 구현 예제 코드
C 언어
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
struct Node* insert(struct Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
void inorder(struct Node* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
printf("Inorder Traversal: ");
inorder(root);
return 0;
}Java
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
public class BST {
Node root;
BST() {
root = null;
}
void insert(int data) {
root = insertRec(root, data);
}
Node insertRec(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data)
root.left = insertRec(root.left, data);
else if (data > root.data)
root.right = insertRec(root.right, data);
return root;
}
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
BST tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
System.out.print("Inorder Traversal: ");
tree.inorder();
}
}Python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, root, data):
if root is None:
return Node(data)
if data < root.data:
root.left = self.insert(root.left, data)
else:
root.right = self.insert(root.right, data)
return root
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.data, end=" ")
self.inorder(root.right)
<em># Usage</em>
bst = BST()
root = None
root = bst.insert(root, 50)
bst.insert(root, 30)
bst.insert(root, 70)
bst.insert(root, 20)
bst.insert(root, 40)
print("Inorder Traversal:", end=" ")
bst.inorder(root)4. 이진 탐색 트리의 장단점
장점
- 빠른 탐색: 평균 시간 복잡도 O(log n).
- 정렬 유지: 삽입 순서와 관계없이 정렬된 데이터 관리.
- 다양한 확장성: AVL, Red-Black Tree로 개선 가능.
단점
- 불균형 문제: 한쪽으로 치우친 트리는 O(n) 시간 복잡도를 가짐.
- 추가 메모리 사용: 포인터와 링크 관리 필요.
5. 이진 탐색 트리의 사용 사례
- 데이터베이스 인덱싱: 효율적인 검색과 정렬.
- 검색 알고리즘: 주어진 값의 존재 여부를 빠르게 확인.
- 네트워크 라우팅: IP 주소 관리와 검색.
- 문자열 자동 완성: 텍스트 예측 및 검색.
- 운영체제 프로세스 관리: 프로세스 우선순위 트리 관리.
