이진 탐색 트리 (BST)

모든 노드에 대해 왼쪽 하위 트리는 자기보다 작고 오른쪽은 크다는 규칙을 지키는 이진 트리입니다.

        8
      /   \
     3     10
    / \      \
   1   6      14

이 규칙에서 두 가지가 따라옵니다.

정렬된 순서를 얻을 수 있다는 점이 해시 테이블과의 결정적 차이입니다. 범위 조회("30에서 50 사이")와 이웃 값 찾기가 가능합니다.

흔한 실수: 규칙을 "왼쪽 자식 < 부모 < 오른쪽 자식"으로 좁게 말하는 것. 하위 트리 전체가 조건을 만족해야 합니다. 자식만 보면 통과하지만 손자에서 깨지는 트리는 BST가 아닙니다.

O(n) 입니다. 트리가 한쪽으로 기울어 사실상 연결 리스트가 되는 경우입니다.

1, 2, 3, 4, 5 를 순서대로 넣으면

1
 \
  2
   \
    3
     \
      4

탐색은 트리의 높이에 비례합니다. 균형이 잡히면 높이가 log n 이지만, 정렬된 데이터를 순서대로 넣으면 높이가 n 이 됩니다. 하필 실무에서 흔한 입력(시간순 id, 정렬된 목록)이 최악을 만듭니다.

흔한 실수: BST의 복잡도를 O(log n)이라고만 답하는 것. 평균이 O(log n)이고 최악이 O(n)입니다. 이 최악을 없애려고 AVL이나 레드블랙 트리처럼 회전으로 높이를 관리하는 구조를 씁니다.

지울 노드 자리에 중위 순회에서 바로 다음 값을 올립니다. 오른쪽 하위 트리의 가장 왼쪽 노드입니다.

        8  <- 지운다
      /   \
     3     10
          /  \
         9    14

오른쪽 하위 트리의 가장 왼쪽은 9
9 를 8 의 자리로 올리고, 원래 9 자리를 정리한다

이 값을 고르는 이유는 지운 값보다 크면서 가장 작은 값이라 BST 규칙이 그대로 유지되기 때문입니다. 왼쪽 하위 트리의 가장 오른쪽 값(지운 값보다 작으면서 가장 큰 값)을 써도 됩니다.

올릴 노드는 자식이 최대 하나이므로(가장 왼쪽이라 왼쪽 자식이 없다) 그 정리는 간단한 경우로 환원됩니다.

흔한 실수: 아무 자식이나 올리는 것. 오른쪽 자식을 그냥 올리면 그 하위 트리의 작은 값들이 규칙을 깨뜨립니다.

높이가 곧 성능이고, 균형이 깨지면 높이가 n 까지 자라기 때문입니다. 균형 트리는 삽입과 삭제 때 회전으로 높이를 log n 안에 묶어둡니다.

읽기가 압도적으로 많으면 AVL, 쓰기가 섞이면 레드블랙이 유리합니다. Java의 TreeMap과 C++의 map 은 레드블랙 트리입니다.

흔한 실수: "균형 트리가 항상 빠르다"고 답하는 것. 회전 비용이 있어 삽입이 잦으면 오히려 느립니다. 그리고 데이터가 이미 무작위 순서로 들어온다면 일반 BST도 평균 log n 입니다.

디스크는 블록 단위로 읽기 때문에, 한 번 읽을 때 최대한 많은 키를 가져오는 구조가 유리합니다.

디스크 접근이 메모리보다 수천 배 느리므로 읽기 횟수를 줄이는 것이 핵심입니다. 노드를 뚱뚱하게 만들어 높이를 낮추는 것이 B-tree 입니다.

리프가 서로 연결된 변형(B+tree)은 범위 조회에도 강합니다. 시작 지점을 찾은 뒤 리프를 따라 순차로 읽으면 됩니다.

흔한 실수: 해시 인덱스가 O(1)이라 더 좋다고 답하는 것. 해시는 등가 조회만 되고 범위 조회와 정렬을 못 합니다. DB 쿼리에는 범위와 ORDER BY 가 흔합니다.

정렬의 강도가 다릅니다. BST는 전체 순서를, 힙은 부모와 자식 사이의 관계만 지킵니다.

그래서 가장 작은 것만 반복해서 꺼내는 우선순위 큐에는 힙을, 정렬된 순회와 범위 조회가 필요하면 BST를 씁니다.

흔한 실수: 힙에서 두 번째로 작은 값을 O(1)에 안다고 답하는 것. 두 자식 중 어느 쪽인지 비교해야 합니다.