이진 탐색 트리 (BST)

이 토픽을 마치면

이진 탐색 트리의 핵심 규칙을 설명할 수 있고, 삽입과 탐색을 코드로 구현할 수 있으며, 중위 순회로 정렬된 데이터를 얻을 수 있습니다.

배열의 한계

정렬된 배열에서 이진 탐색은 O(log n)으로 빠릅니다. 하지만 삽입과 삭제가 느립니다 — 중간에 값을 넣으려면 나머지를 밀어야 하기 때문입니다:

text

[2, 5, 8, 12, 15]
     ↑ 여기에 7을 넣으려면
[2, 5, 7, 8, 12, 15]  ← 8, 12, 15를 오른쪽으로 밀어야 함 (O(n))

검색도 빠르고 삽입도 빠른 자료구조가 필요합니다. 이것이 이진 탐색 트리입니다.

핵심 규칙

이진 탐색 트리(Binary Search Tree, BST)는 하나의 규칙만 지킵니다:

왼쪽 자식 < 부모 < 오른쪽 자식

text

8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

어느 노드를 보더라도, 왼쪽 서브트리의 모든 값은 자기보다 작고, 오른쪽 서브트리의 모든 값은 자기보다 큽니다.

노드 구현

python

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

각 노드는 값 하나와 왼쪽/오른쪽 자식을 가리키는 포인터 두 개를 갖습니다.

삽입

새 값을 넣을 때, 루트부터 시작해서 규칙에 따라 내려갑니다:

python

def insert(root, value):
    if root is None:
        return Node(value)
    
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    
    return root

python

# 트리 만들기
root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)

값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 갑니다. 빈 자리를 찾으면 거기에 새 노드를 만듭니다.

탐색

python

def search(root, target):
    if root is None:
        return False
    
    if target == root.value:
        return True
    elif target < root.value:
        return search(root.left, target)
    else:
        return search(root.right, target)

python

print(search(root, 7))   # True
print(search(root, 5))   # False

이진 탐색과 같은 원리입니다. 매 단계마다 절반을 버리므로, 균형 잡힌 트리에서는 **O(log n)**입니다.

탐색 과정 (7을 찾을 때):

text

8 → 7 < 8, 왼쪽
3 → 7 > 3, 오른쪽
6 → 7 > 6, 오른쪽
7 → 찾았다!

중위 순회 — 정렬된 결과

트리를 "왼쪽 → 자신 → 오른쪽" 순서로 방문하면 정렬된 순서로 값을 얻습니다. 이것을 중위 순회(in-order traversal)라고 합니다.

python

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.value] + inorder(root.right)

print(inorder(root))  # [1, 3, 4, 6, 7, 8, 10, 13, 14]

BST의 규칙(왼쪽 < 부모 < 오른쪽)을 따라 왼쪽부터 방문하면 자연스럽게 오름차순이 됩니다. 별도의 정렬 알고리즘 없이 정렬된 데이터를 얻는 것입니다.

세 가지 순회

python

def preorder(root):   # 전위: 자신 → 왼쪽 → 오른쪽
    if root is None: return []
    return [root.value] + preorder(root.left) + preorder(root.right)

def postorder(root):  # 후위: 왼쪽 → 오른쪽 → 자신
    if root is None: return []
    return postorder(root.left) + postorder(root.right) + [root.value]

python

print(preorder(root))   # [8, 3, 1, 6, 4, 7, 10, 14, 13]
print(inorder(root))    # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(postorder(root))  # [1, 4, 7, 6, 3, 13, 14, 10, 8]

순회	순서	용도
전위 (preorder)	자신 → 왼 → 오	트리 복사, 직렬화
중위 (inorder)	왼 → 자신 → 오	정렬된 출력
후위 (postorder)	왼 → 오 → 자신	트리 삭제, 수식 트리 평가

최악의 경우

BST의 성능은 트리의 균형에 달려있습니다:

text

# 균형 트리 (O(log n))     # 편향 트리 (O(n)) — 사실상 연결 리스트
        8                    1
       / \                    \
      3   10                   2
     / \    \                   \
    1   6    14                  3
                                  \
                                   4

정렬된 데이터를 순서대로 삽입하면 편향 트리가 됩니다. 이 문제를 해결하기 위해 AVL 트리나 Red-Black 트리 같은 자가 균형 트리가 있습니다. Python의 sorted(), Java의 TreeMap 내부에서 이런 균형 트리를 사용합니다.

시간 복잡도 정리

연산	평균	최악 (편향)
탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)
순회	O(n)	O(n)

BST 삭제 — 세 가지 경우

삭제는 BST에서 가장 복잡한 연산입니다:

python

def delete(root, value):
    if root is None:
        return None
    
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        # 경우 1: 자식이 없음 (리프) — 그냥 삭제
        if root.left is None and root.right is None:
            return None
        # 경우 2: 자식이 하나 — 자식이 자리를 대체
        elif root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        # 경우 3: 자식이 둘 — 후계자로 교체
        else:
            successor = find_min(root.right)
            root.value = successor.value
            root.right = delete(root.right, successor.value)
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node

자식이 둘인 노드를 삭제할 때, 오른쪽 서브트리의 최소값(중위 후계자)으로 교체합니다. BST의 정렬 조건이 유지됩니다.

실무에서 BST를 직접 쓰는가

Python에는 BST 내장 모듈이 없습니다. 대신:

python

from bisect import insort, bisect_left

sorted_list = []
insort(sorted_list, 5)   # 정렬 유지하며 삽입
insort(sorted_list, 3)
insort(sorted_list, 7)
print(sorted_list)  # [3, 5, 7]

idx = bisect_left(sorted_list, 5)  # 이진 탐색
print(sorted_list[idx])  # 5

bisect 모듈은 정렬된 리스트에서 BST와 유사한 O(log n) 탐색을 제공합니다. 삽입은 O(n)(배열 밀기)이므로 삽입이 빈번하면 SortedContainers 같은 서드파티 라이브러리를 사용합니다.

BST vs 해시 테이블 vs 정렬 배열

연산	BST (균형)	해시 테이블	정렬 배열
검색	O(log n)	O(1) 평균	O(log n)
삽입	O(log n)	O(1) 평균	O(n)
삭제	O(log n)	O(1) 평균	O(n)
최소/최대	O(log n)	O(n)	O(1)
범위 검색	O(log n + k)	O(n)	O(log n + k)
정렬 출력	O(n)	O(n log n)	O(n)

해시 테이블이 빠르지만 "정렬 순서"가 필요하면 BST가 유리합니다. "100 이상 200 이하인 값"처럼 범위 질의가 필요한 데이터베이스 인덱스가 대표적입니다.

BST는 "정렬된 데이터를 동적으로 유지"해야 할 때 적합합니다. 배열과 연결 리스트의 장점을 결합한 자료구조입니다.