# BST (Binary Search Tree)

**BST**(Binary Search Tree, **이진 탐색 트리**)는 데이터 구조의 일종으로, 각 노드가 최대 두 개의 자식 노드를 가지며, 노드 간의 값이 특정 순서 규칙을 따라 배치된 트리 구조입니다. 이 구조는 검색, 삽입, 삭제 연산에서 평균적으로 $O(\log n)$의 시간 복잡도를 제공하여 대규모 데이터 처리에 효율적입니다.

## 개요

이진 탐색 트리는 배열이나 연결 리스트와 같은 선형 자료구조의 단점을 보완하기 위해 고안되었습니다. 배열은 정렬된 상태라면 이진 탐색을 통해 빠르게 검색할 수 있지만, 삽입과 삭제 시 데이터 이동이 필요하여 비효율적입니다. 반면, 연결 리스트는 삽입과 삭제는 빠르지만 검색에 $O(n)$의 시간이 소요됩니다. BST는 이 두 가지 장점을 결합하여, 정렬된 상태를 유지하면서도 동적인 데이터 조작이 가능하도록 설계되었습니다.

BST의 핵심 원리는 **이진 탐색 원리(Binary Search Principle)**에 기반합니다. 루트(Root) 노드에서 시작하여 목표 값과 현재 노드의 값을 비교합니다. 목표 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동합니다. 이 과정을 트리의 리프(Leaf) 노드에 도달하거나 목표 값을 찾을 때까지 반복합니다.

## 구조적 특징

BST는 다음과 같은 엄격한 구조적 규칙을 따릅니다.

1. **이진성(Binary Property)**: 각 노드는 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가집니다.
2. **정렬 규칙(Sorting Property)**:
   - 어떤 노드의 **왼쪽 서브트리**에 있는 모든 노드의 키(Key)는 해당 노드의 키보다 **작습니다**.
   - 어떤 노드의 **오른쪽 서브트리**에 있는 모든 노드의 키는 해당 노드의 키보다 **큽니다**.
3. **재귀적 구조**: 왼쪽과 오른쪽 서브트리 또한 각각 이진 탐색 트리의 성질을 만족해야 합니다.

### 노드의 구성 요소

일반적으로 BST의 노드는 다음과 같은 필드로 구성됩니다.

| 필드명 | 설명 |
| :--- | :--- |
| `key` | 노드에 저장된 데이터 값 (검색의 기준이 됨) |
| `left` | 왼쪽 자식 노드를 가리키는 포인터 또는 참조 |
| `right` | 오른쪽 자식 노드를 가리키는 포인터 또는 참조 |
| `parent` | 부모 노드를 가리키는 포인터 (선택적) |

## 주요 연산과 알고리즘

BST의 유용성은 효율적인 연산 알고리즘에서 비롯됩니다.

### 1. 검색 (Search)
목표 값이 트리에 존재하는지 확인합니다.
- **시간 복잡도**: 평균 $O(\log n)$, 최악 $O(n)$ (편향된 트리의 경우)
- **알고리즘**:
  1. 루트에서 시작합니다.
  2. 현재 노드의 키와 목표 값을 비교합니다.
  3. 같으면 검색 성공.
  4. 목표 값이 작으면 왼쪽 자식으로 이동.
  5. 목표 값이 크면 오른쪽 자식으로 이동.
  6. 노드가 null이 될 때까지 반복.

### 2. 삽입 (Insertion)
새로운 값을 트리의 올바른 위치에 추가합니다.
- **시간 복잡도**: 평균 $O(\log n)$, 최악 $O(n)$
- **알고리즘**:
  1. 검색 과정과 유사하게 목표 값이 삽입되어야 할 위치(리프 노드의 자식 위치)를 찾습니다.
  2. 해당 위치에 새 노드를 생성하여 연결합니다.
  3. BST의 정렬 규칙을 유지하기 위해 부모 노드와의 관계를 올바르게 설정해야 합니다.

### 3. 삭제 (Deletion)
특정 값을 가진 노드를 제거합니다. 삭제는 노드의 자식 노드 수에 따라 세 가지 경우로 나뉩니다.
- **시간 복잡도**: 평균 $O(\log n)$, 최악 $O(n)$
- **경우 1: 리프 노드인 경우**
  - 단순히 노드를 제거하면 됩니다.
- **경우 2: 자식 노드가 하나인 경우**
  - 제거할 노드를 부모가 직접 자식 노드와 연결하면 됩니다.
- **경우 3: 자식 노드가 두 개인 경우**
  - **중위 후속자(In-order Successor)** 또는 **중위 선행자(In-order Predecessor)**를 사용합니다.
  - 일반적으로 오른쪽 서브트리에서 가장 작은 값(중위 후속자)을 찾아 제거할 노드의 위치로 옮긴 후, 원래 위치의 노드를 삭제합니다. 이는 BST의 정렬 순서를 유지하는 핵심 기법입니다.

## 시간 복잡도 분석

BST의 성능은 트리의 균형(Balance)에 크게 의존합니다.

| 시나리오 | 트리 형태 | 검색/삽입/삭제 복잡도 | 설명 |
| :--- | :--- | :--- | :--- |
| **평균 경우** | 균형 잡힌 트리 | $O(\log n)$ | 노드가 균일하게 분포되어 트리의 높이가 $\log_2 n$에 가까움 |
| **최악 경우** | 편향된 트리 (선형) | $O(n)$ | 데이터가 정렬된 순서로 삽입될 경우, 트리가 한쪽으로 치우쳐 연결 리스트와 유사해짐 |

## 한계와 개선 방안

표준 BST는 데이터의 삽입 순서에 따라 트리의 균형이 무너질 수 있어, 최악의 경우 성능이 선형 자료구조와 동일해집니다. 이를 해결하기 위해 다양한 **균형 이진 탐색 트리(Balanced BST)** 알고리즘이 개발되었습니다.

- **AVL Tree**: 임의의 노드에서 왼쪽과 오른쪽 서브트리의 높이가 최대 1만 차이나도록 회전(Rotation) 연산을 통해 균형을 유지합니다.
- **Red-Black Tree**: 노드를 빨강/검정으로 색칠하여 트리의 높이가 최대 $2\log(n+1)$이 되도록 보장합니다. 리눅스 커널의 CFS(Completely Fair Scheduler)나 자바의 `TreeMap` 등에 널리 사용됩니다.
- **B-Tree / B+ Tree**: 디스크 기반 데이터베이스의 인덱싱에 주로 사용되며, 하나의 노드가 여러 개의 키를 가질 수 있어 트리의 높이를 최소화합니다.

## 관련 문서 및 참고 자료

- **이진 트리 (Binary Tree)**: BST의 기반이 되는 기본 트리 구조
- **그래프 이론 (Graph Theory)**: 트리는 사이클이 없는 특수한 그래프입니다.
- **해시 테이블 (Hash Table)**: 평균 $O(1)$ 검색 속도를 제공하지만, 정렬된 데이터 처리에는 BST가 더 적합할 수 있습니다.
- **알고리즘 설계 (Algorithm Design)**: 클리퍼드 스타인츠 등, BST의 구현과 분석에 대한 심화 학습 자료

---
*본 문서는 이진 탐색 트리의 기본 개념, 구조, 연산, 그리고 한계점을 기술하였습니다. 실제 시스템 구현 시에는 균형 유지 알고리즘(AVL, Red-Black 등)을 고려하여 설계하는 것이 권장됩니다.*