이진 탐색 트리 (BST)

BST의 본질 (불변식)

• BST(Binary Search Tree)는 다음 불변식을 만족하는 이진 트리입니다.
  • 임의의 노드 X에 대해: 왼쪽 서브트리의 모든 값 < X < 오른쪽 서브트리의 모든 값
• 이 규칙이 모든 서브트리에서 재귀적으로 성립해야 합니다.
• 이 불변식 덕분에 탐색/삽입/삭제가 "비교하며 한쪽만 내려가는" 형태가 됩니다.

struct Node {
    int key;
    Node* left = nullptr;
    Node* right = nullptr;
};

BST 구조 예시

        [10]
       /    \
     [5]    [15]
     / \    /  \
   [3] [8][12][20]

In-Order(중위 순회): 3 -> 5 -> 8 -> 10 -> 12 -> 15 -> 20 (오름차순)

---

연산 복잡도 한눈에 보기

트리 높이를 h라고 하면 대부분 연산은 O(h)입니다.

연산	복잡도
search	O(h)
insert	O(h)
delete	O(h)
min / max	O(h)

• 균형이 잘 잡히면 h ~= log N -> O(log N)
• 한쪽으로 치우치면 h ~= N -> O(N)

---

search (탐색)

Node* Search(Node* root, int key) {
    Node* cur = root;
    while (cur) {
        if (key == cur->key) return cur;
        if (key < cur->key) cur = cur->left;
        else cur = cur->right;
    }
    return nullptr;
}

• 매 단계에서 왼쪽/오른쪽 중 한쪽만 선택하므로 O(h).

---

insert (삽입)

• 루트부터 비교하면서 내려가 빈 자리를 찾은 뒤 새 노드를 연결합니다.
• 중복 키 처리 정책은 구현마다 다릅니다(중요).
  • 삽입 무시
  • 빈도(count) 증가
  • 한쪽(예: 오른쪽)에 모아 저장

Node* Insert(Node* root, int key) {
    if (!root) return new Node{key};
    if (key < root->key) root->left = Insert(root->left, key);
    else if (key > root->key) root->right = Insert(root->right, key);
    // else: 중복 정책 처리
    return root;
}

---

delete (핵심: 3가지 케이스)

삭제 대상 노드 상태	처리 방식
자식 0개(리프)	그냥 제거
자식 1개	자식을 부모와 직접 연결
자식 2개	후속자(successor) 또는 전임자(predecessor)로 대체 후 재삭제

자식 2개 케이스(가장 중요):

1. 삭제 노드의 후속자(오른쪽 서브트리의 최소값)를 찾음
2. 후속자 값을 삭제 대상 노드에 복사
3. 원래 후속자 노드를 삭제 (후속자는 구조상 자식이 0개 또는 1개)

Node* FindMin(Node* x) {
    while (x && x->left) x = x->left;
    return x;
}

---

min / max / next(후속자) / prev(전임자)

• min: 왼쪽으로 끝까지 이동
• max: 오른쪽으로 끝까지 이동
• next(in-order successor):
  • 오른쪽 자식이 있으면 -> 오른쪽 서브트리의 min
  • 없으면 -> "해당 노드를 왼쪽 자식으로 포함하는 최초 조상"
• prev(in-order predecessor)는 위 규칙의 좌우 반대

next 찾기 직관

케이스 A) 오른쪽 있음
   node=10, right=15 -> next = min(15-subtree) = 12

케이스 B) 오른쪽 없음
   부모로 올라가며 "내가 왼쪽 자식이 되는 첫 조상"을 찾음

---

한계: 균형이 깨지면 느려진다

정렬된 값이 순서대로 들어오면 아래처럼 편향 트리가 됩니다.

1
 \
  2
   \
    3
     \
      4

• 높이가 N에 가까워져 탐색/삽입/삭제가 O(N)으로 악화됩니다.
• 이를 막기 위해 AVL, Red-Black Tree 같은 자가 균형 BST가 사용됩니다.

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
BST 규칙을 "부모와 자식만" 비교로 이해	서브트리 전체 조건 위반 가능
삭제 2자식 케이스에서 후속자 노드 자체를 잘못 연결	트리 구조 깨짐/메모리 오류
중복 키 정책을 정하지 않고 구현	동작 불일치/버그
복잡도를 항상 O(log N)으로 단정	편향 트리에서 O(N)

체크 질문 (스스로 답해보기)

• 왜 BST의 탐색/삽입/삭제 복잡도를 O(h)로 표현하는가?
• 삭제 대상이 자식 2개일 때 왜 후속자를 쓰면 구현이 단순해지는가?
• 편향 트리가 되는 입력 패턴을 하나 들고, 왜 느려지는지 설명할 수 있는가?

---