이진 탐색 트리: 검색할 수 있는 순서

"해시맵은 즉시 조회를 주지만 순서는 제로. 이진 탐색 트리는 둘 다 줘 — 조회 그리고 순서 — 모든 노드에서 단순한 규칙 하나를 강제해서."

단 하나의 불변식

이진 탐색 트리 (BST) 는 깨질 수 없는 규칙 하나가 있는 이진 트리야: 모든 노드에 대해, 그 왼쪽 서브트리 키는 다 작고, 오른쪽 서브트리 키는 다 크다. 그 불변식이 재귀적으로, 모든 노드에서, 끝까지 성립해. 거기서 모든 게 거의 공짜로 따라 나와.

검색: 루트에서 시작, 비교. 작아? 왼쪽. 커? 오른쪽. 각 비교가 서브트리 전체를 버려서, 매 단계 탐색 공간 절반 — 균형 잡혔을 때 O(log n). 말 그대로 이진 탐색을 살아있는 구조로 만든 거야. 삽입: 키가 있을 자리를 검색하고, 거기 새 리프로 붙여. 중위 순회 (left-노드-right) 가 키를 정렬 순서로 걸어, 공짜로 — 지난 lesson 의 속성.

해싱 사각지대에 대한 답

해싱의 실패 기억해: 순서 없음, 범위 쿼리 없음. BST 가 정확히 그 간극을 메우는 구조야. 해시맵이 못 하는 걸 해:

min / max — 끝까지 왼쪽 / 끝까지 오른쪽 걷기: O(log n).
정렬 순회 — 중위 순회: O(n), 이미 순서대로.
범위 쿼리 — "10 과 20 사이 모든 키" — 범위 밖 서브트리 가지치기.
floor / ceiling — "x 이하 가장 큰 키" / "x 이상 가장 작은 키" — 검색 경로에서 떨어져.

그래서 "빠른 조회 그리고 순서가 필요해" 가 해시맵에서 트리로 보내. 경쟁자가 아니라 상보적 도구야.

BST 불변식: 모든 노드에서 왼쪽 서브트리 < 노드 < 오른쪽 서브트리. 그게 균형 잡혔을 때 O(log n) 검색/삽입/삭제, 공짜 정렬 중위 순회, 더해서 min/max/범위/floor/ceiling — 정확히 해시맵이 못 하는 순서 연산을 줘.

다음 lesson 을 세우는 함정

그 모든 O(log n) 좋음엔 치명적 별표가 있어: 균형 잡혔을 때만 성립해. 키를 정렬 순서 (1, 2, 3, 4, 5…) 로 평범한 BST 에 삽입하면 각 새 키가 오른쪽, 오른쪽, 오른쪽 — 트리가 트리 옷 입은 연결 리스트, 한쪽 사슬로 퇴화해. 이제 검색이 O(n) 이고, 전부를 잃었어. 정렬-ish 입력이 현실에서 극도로 흔해서, 이건 드문 엣지 케이스가 아니라 — 기본 실패야. 그걸 고치는 게 다음 lesson, 균형 잡기의 전부야.

피파의 고백

난 BST 를 짓고, 무작위 데이터로 테스트하고, 아름다운 O(log n) 을 보고, 자랑스럽게 출시했어. 그러다 이미 정렬된 입력을 먹고 재귀 한계를 터뜨리는 10,000 깊이 사슬이 됐어. 아빠가 그냥 끄덕였어: "평범한 BST 는 입력이 섞였다고 믿어. 진짜 입력은 거의 안 그래." 그 멍이 '데모에선 됨' 이랑 'production 에서 살아남음' 의 차이를 — 그리고 내가 까다롭다고 무시한 균형 트리가 대체 왜 존재하는지 가르쳤어.

Code

BST 삽입/검색, 그리고 정렬-입력 함정·python

class BSTNode:
    def __init__(self, key): self.key = key; self.left = None; self.right = None

def insert(root, key):
    if root is None:
        return BSTNode(key)              # 빈 자리 찾음 -> 리프로 붙여
    if key < root.key:
        root.left = insert(root.left, key)   # 작음 -> 왼쪽
    elif key > root.key:
        root.right = insert(root.right, key) # 큼   -> 오른쪽
    return root

def search(root, key):                   # 균형 잡혔을 때 O(log n)
    while root:
        if key == root.key: return True
        root = root.left if key < root.key else root.right  # 매 단계 절반
    return False

def inorder(root):                       # 왼쪽, 노드, 오른쪽 -> 정렬됨
    if root is None: return []
    return inorder(root.left) + [root.key] + inorder(root.right)

# 균형-ish 삽입 순서:
balanced = None
for k in [4, 2, 6, 1, 3, 5, 7]:
    balanced = insert(balanced, k)
print("search 5:", search(balanced, 5))   # True
print("sorted  :", inorder(balanced))      # [1,2,3,4,5,6,7] — 순서, 공짜로

# 함정: 정렬 순서 삽입이 사슬로 퇴화.
degenerate = None
for k in [1, 2, 3, 4, 5]:
    degenerate = insert(degenerate, k)     # 각자 오른쪽 -> 연결 리스트!
# 'degenerate' 는 이제 높이 4 (O(n) 검색), 높이 ~2 아니라. 같은 코드, 나쁜 입력.

Exercise

키 8, 3, 10, 1, 6 을 그 순서로 빈 BST 에 삽입하고, 나온 모양을 그려. 그다음 6 검색을 추적해: 어느 노드를 방문해? 마지막으로, 같은 다섯 키를 정렬 순서 (1, 3, 6, 8, 10) 로 삽입하면 왜 훨씬 나쁜 트리가 나오는지, 그 높이가 뭐가 되는지 설명해.

Hint

8 이 루트; 3 왼쪽, 10 오른쪽; 1 은 3 의 왼쪽, 6 은 3 의 오른쪽. 6 검색: 8 → 3 → 6, 세 노드. 정렬 삽입은 1→3→6→8→10 을 높이 4 오른쪽 기운 사슬로 만들어 — 연결 리스트, O(n) 검색.

단 하나의 불변식

해싱 사각지대에 대한 답

다음 lesson 을 세우는 함정

피파의 고백

Code

External links

Exercise

Progress

댓글 0