binary search tree(BST)란 무엇이며, 그 연산 복잡도는 어떻게 되나요?

Question

Accepted Answer

**binary search tree(이진 탐색 트리)**는 순서 불변식(ordering invariant)을 가진 binary tree입니다. 모든 노드에 대해 **왼쪽 서브트리의 모든 key는 더 작고**, **오른쪽 서브트리의 모든 key는 더 큽니다**. 이로써 각 단계마다 문제를 절반으로 줄이며 검색할 수 있습니다.

## 불변식

```text
        8
       / \
      3    10
     / \     \
    1   6     14     모든 노드에서 left < node < right
```

## 검색과 삽입

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # 한쪽으로 진행
    return None

def insert(node, key):
    if node is None: return Node(key)
    if key < node.val: node.left  = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## 복잡도

| 연산 | 균형 | 최악(퇴화) |
|---|---|---|
| 검색 | O(log n) | O(n) |
| 삽입 | O(log n) | O(n) |
| 삭제 | O(log n) | O(n) |

**최악의 경우**는 key가 정렬된 순서로 삽입될 때 발생합니다. 트리가 높이 `n`의 linked list로 퇴화합니다.

## 트레이드오프

- **강점:** O(n)에 정렬된 순회; 범위 질의와 후행자/선행자 지원.
- **약점:** 자체적으로는 균형 보장이 없음 — O(log n)을 유지하려면 AVL이나 red-black 변형이 필요함.

## 왜 중요한가

BST는 로그 시간 연산으로 정렬된 동적 데이터를 제공합니다. 데이터베이스 인덱스와 ordered map의 개념적 조상입니다.

퇴화 문제는 면접에서 핵심 후속 주제인 **자가 균형 트리(self-balancing tree)**의 동기가 됩니다.