이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리(Binary Search Tree, BST)는 모든 노드에 대해 왼쪽 부분 트리에는 자신보다 작은 값만, 오른쪽 부분 트리에는 자신보다 큰 값만 오도록 정렬 규칙을 부여한 이진 트리다. 이진 탐색 트리는 이 규칙 덕분에 탐색, 삽입, 삭제를 평균 O(log n)에 처리하면서도 데이터를 항상 정렬된 상태로 유지한다. 다만 삽입 순서에 따라 트리가 한쪽으로 기울면 성능이 O(n)까지 나빠지므로, 실무에서는 균형을 스스로 잡는 변형이 함께 쓰인다.

핵심 불변식과 탐색 원리

이진 탐색 트리의 규칙은 특정 노드와 자식 사이만이 아니라 부분 트리 전체에 적용된다는 점이 중요하다. 즉 어떤 노드의 왼쪽 자손 전부가 그 노드보다 작아야 한다. 이 불변식(invariant)이 지켜지면 탐색은 이진 탐색(binary search)과 같은 원리로 동작한다. 루트에서 시작해 찾는 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 내려가며, 한 번 비교할 때마다 후보 범위가 부분 트리 하나로 좁혀진다. 비교 횟수는 트리의 높이만큼이므로 균형 잡힌 트리에서는 O(log n)이다.

또 하나의 중요한 성질은 중위 순회(inorder traversal)를 하면 모든 값이 오름차순으로 나온다는 것이다. 이 성질은 어떤 이진 트리가 올바른 BST인지 검증하는 문제의 열쇠이기도 하다.

삽입과 삭제

삽입은 탐색과 같은 경로를 따라 내려가다가 널(null)을 만나는 자리에 새 노드를 붙이면 된다. 삭제는 세 경우로 나뉜다. 자식이 없는 리프는 그냥 제거한다. 자식이 하나면 그 자식을 부모에 직접 연결한다. 자식이 둘이면 오른쪽 부분 트리의 최솟값(중위 후속자, inorder successor)이나 왼쪽 부분 트리의 최댓값(중위 선행자)을 찾아 삭제할 노드의 값을 대체한 뒤, 그 후속자 노드를 재귀적으로 삭제한다. 후속자는 자식이 최대 하나뿐이므로 재귀는 앞의 두 경우로 귀결된다.

시간 복잡도와 퇴화 문제

연산	평균(균형 상태)	최악(편향 상태)
탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)
정렬된 전체 순회	O(n)	O(n)

최악의 경우는 이미 정렬된 데이터를 순서대로 삽입할 때다. 1, 2, 3, 4를 차례로 넣으면 모든 노드가 오른쪽 자식만 갖는 편향 트리가 되어 사실상 연결 리스트로 퇴화한다. 이 문제를 해결한 것이 자가 균형 이진 탐색 트리(self-balancing BST)다. AVL 트리는 양쪽 부분 트리의 높이 차를 1 이하로 엄격히 유지해 탐색이 빠른 대신 삽입과 삭제 때 회전(rotation)이 잦고, 레드 블랙 트리(Red-Black Tree)는 색 규칙으로 느슨한 균형을 유지해 수정 비용이 상대적으로 작다. 자바(Java)의 TreeMap과 TreeSet, C++의 map과 set이 레드 블랙 트리로 구현되어 있어, 이들 컨테이너의 연산이 항상 O(log n)으로 보장되는 근거가 된다.

class Node {
    int key;
    Node left, right;
    Node(int key) { this.key = key; }
}

boolean search(Node node, int key) {
    if (node == null) return false;
    if (key == node.key) return true;
    return key < node.key ? search(node.left, key)
                          : search(node.right, key);
}

Node insert(Node node, int key) {
    if (node == null) return new Node(key);
    if (key < node.key) node.left = insert(node.left, key);
    else if (key > node.key) node.right = insert(node.right, key);
    return node; // 중복 키는 무시하는 정책
}