이진 탐색 트리가 O(log n)을 잃는 순간

이진 탐색 트리(BST)의 탐색이 O(log n)이라는 설명은 절반만 맞습니다. 정확히는 트리의 높이에 비례하고, 높이가 log n이 되는 건 트리가 균형을 유지할 때뿐입니다.

직접 넣어보기

아래에 값을 넣으면서 높이가 어떻게 변하는지 보세요. 1, 2, 3, 4, 5처럼 오름차순으로 넣는 경우와, 4, 2, 6, 1, 3 처럼 섞어서 넣는 경우를 비교하면 차이가 분명합니다.

같은 7개 값인데 높이가 7과 3으로 갈립니다. 탐색 비용이 7번 비교와 3번 비교의 차이이고, 노드가 100만 개면 100만 번과 20번의 차이가 됩니다.

편향이 왜 생기나

BST 삽입은 루트부터 내려가며 자리를 찾습니다. 오름차순 데이터를 넣으면 새 값이 항상 직전 값보다 커서, 매번 오른쪽 자식으로만 내려갑니다. 결과는 오른쪽으로만 뻗은 연결 리스트입니다.

문제는 이게 드문 상황이 아니라는 점입니다. DB에서 정렬해 가져온 결과, 시간순 로그, 자동 증가 ID — 실무 데이터는 이미 정렬돼 있는 경우가 많습니다.

final class BSTNode<T: Comparable> {
    let value: T
    var left: BSTNode?
    var right: BSTNode?

    init(_ value: T) { self.value = value }

    func insert(_ new: T) {
        if new < value {
            if let left { left.insert(new) } else { left = BSTNode(new) }
        } else if new > value {
            if let right { right.insert(new) } else { right = BSTNode(new) }
        }
    }
}

이 구현에는 균형을 맞추는 코드가 한 줄도 없습니다. 그래서 입력 순서가 곧 성능이 됩니다.

균형 트리가 하는 일

AVL 트리와 레드-블랙 트리는 삽입·삭제 때마다 회전으로 높이를 log n 수준에 묶어둡니다.

AVL: 좌우 서브트리 높이 차를 1 이하로 유지. 더 엄격해서 탐색이 빠르고, 대신 삽입·삭제 때 회전이 잦습니다.
레드-블랙: 색 규칙으로 최장 경로가 최단 경로의 2배를 넘지 않게 유지. 회전이 덜 일어나서 쓰기가 많은 쪽에 유리합니다.

Java의 TreeMap, C++의 std::map, 리눅스 커널 스케줄러가 레드-블랙 트리를 씁니다. 읽기와 쓰기가 섞인 일반적인 상황에서 무난하기 때문입니다.

Swift에는 왜 트리 자료구조가 없나

표준 라이브러리에 TreeMap 같은 게 없습니다. Dictionary와 Set이 해시 기반이라 평균 O(1)이고, 정렬된 순회가 필요한 경우가 상대적으로 적어서입니다.

정렬 순서를 유지해야 한다면 선택지는 두 가지입니다.

swift-collections의 OrderedDictionary — 삽입 순서 유지. 정렬 순서는 아닙니다.
배열을 정렬 상태로 유지하고 이진 탐색으로 삽입 위치 찾기 — 탐색 O(log n), 삽입은 원소 이동 때문에 O(n)

원소가 수천 개 수준이면 정렬 배열이 트리보다 빠른 경우도 많습니다. 메모리가 연속이라 캐시를 잘 쓰기 때문입니다.

면접에서 나오면

“BST의 시간복잡도는?”에 O(log n)만 답하면 절반입니다. 이렇게 답하는 게 낫습니다.

평균 O(log n)이지만 정확히는 트리 높이에 비례합니다. 정렬된 데이터를 순서대로 넣으면 한쪽으로 편향돼 O(n)이 되고, 이걸 막으려고 AVL이나 레드-블랙 같은 균형 트리를 씁니다.

다음 글에서는 그래프 표현 방식(인접 행렬 vs 인접 리스트)과 선택 기준을 다루겠습니다.