이진 탐색 트리란? 동작 원리, 코드, 시간 복잡도

이진 탐색 트리가 해결하는 문제

정렬된 배열은 이진 탐색이 빠르지만, 새 요소를 삽입하면 그 뒤의 모든 요소가 밀려납니다. 해시 테이블은 조회와 삽입이 빠르지만 순서를 유지하지 않아서 "42보다 큰 키 중 가장 작은 것은?"이나 "10에서 20 사이의 키를 모두 나열하라" 같은 질문에는 답할 수 없습니다. 이진 탐색 트리는 키를 정렬된 상태로 유지하면서도 삽입과 삭제를 빠르게 할 수 있습니다. 스스로 균형을 잡는 변형을 사용하는 Java의 TreeMap, C++의 std::map 같은 순서 있는 맵과 집합의 기반입니다.

쉬운 말로 설명하는 규칙

각 노드는 키 하나와 선택적인 왼쪽 자식, 오른쪽 자식을 가집니다. 모든 노드에 대해 왼쪽 서브트리의 키는 모두 더 작고, 오른쪽 서브트리의 키는 모두 더 큽니다. 키를 찾으려면 루트에서 시작해 비교합니다. 키가 더 작으면 왼쪽으로, 더 크면 오른쪽으로 가고, 같으면 멈추며, 트리 밖으로 벗어나도 멈춥니다.

예제: 트리 만들고 검색하기

8, 3, 10, 1, 6, 14, 4를 이 순서대로 삽입합니다. 새 키는 루트에서 내려가다가 트리 밖으로 벗어나는 지점에서 리프가 됩니다.

4를 검색하면 8, 3, 6, 4와 차례로 비교합니다. 키가 7개인 트리에서 비교 4번입니다. 7을 검색하면 8, 3, 6과 비교한 뒤 6에 오른쪽 자식이 없으므로 7은 없다는 것을 알 수 있습니다.

파이썬 구현

삽입과 검색은 짧은 반복문입니다. 삭제에는 세 가지 경우가 있습니다. 노드에 자식이 없으면 제거하고, 자식이 하나면 그 자식으로 교체하고, 자식이 둘이면 중위 후속자(오른쪽 서브트리에서 가장 작은 키)를 복사해 넣은 뒤 그 후속자를 삭제합니다.

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored
def contains(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

root = None
for k in [8, 3, 10, 1, 6, 14, 4]:
    root = insert(root, k)
print(inorder(root))                 # [1, 3, 4, 6, 8, 10, 14]
print(contains(root, 4), contains(root, 7))  # True False
root = delete(root, 3)               # node with two children
print(inorder(root), root.left.key)  # [1, 4, 6, 8, 10, 14] 4

시간 복잡도와 공간 복잡도

최악의 경우는 이론에만 있는 것이 아닙니다. 이미 정렬된 키(1, 2, 3, ...)를 일반 BST에 삽입하면 모든 노드가 오른쪽 자식만 갖게 되어 트리가 연결 리스트가 됩니다. 삽입 순서가 무작위이면 기대 높이는 O(log n)입니다.

균형 잡힌 변형과 흔한 실수

스스로 균형을 잡는 트리는 삽입과 삭제 후 회전으로 구조를 바꿔 높이를 O(log n)으로 유지합니다.

• 부모와 자식만 확인해서 BST를 검증하는 실수. 대신 유효한 (low, high) 범위를 아래로 넘겨 주세요.
• 재귀 삽입·삭제에서 (새로 바뀌었을 수 있는) 루트를 반환하지 않아 변경이 사라지는 실수.
• 퇴화한 트리에서의 깊은 재귀: 파이썬의 기본 재귀 한도는 약 1000이므로 노드 5000개짜리 체인에서는 재귀 코드가 비정상 종료됩니다. 반복문을 쓰거나 트리의 균형을 유지하세요.
• 중복 처리 정책을 정하지 않는 실수: 중복을 무시할지, 개수를 셀지, 항상 한쪽에 둘지 정해야 합니다.

BST를 쓸 때와 면접 단골 문제

삽입과 삭제가 잦으면서 정렬된 데이터가 필요할 때 균형 BST를 사용하세요. 범위 질의, floor·ceiling 조회, 순위 통계, 정렬된 순서의 순회가 그런 경우입니다. 정확한 키 조회만 필요하다면 해시 테이블을 쓰세요. 파이썬 표준 라이브러리에는 트리 맵이 없습니다. 작거나 거의 변하지 않는 데이터에는 bisect 모듈과 정렬된 리스트, 그 밖에는 서드파티 패키지 sortedcontainers를 흔히 선택합니다.

대표적인 면접 문제: BST 검증, k번째로 작은 요소 찾기(중위 순회), 최소 공통 조상, 정렬된 배열을 균형 BST로 변환하기(가운데 요소를 루트로 선택), 노드의 중위 후속자 찾기.