"해시맵은 즉시 조회를 주는 대신 순서는 하나도 안 줘. 이진 탐색 트리는 둘 다 줘. 조회와 순서를 동시에. 모든 노드에서 단순한 규칙 하나를 지키게 하는 것만으로."
단 하나의 불변식
이진 탐색 트리(BST)는 절대 깨지면 안 되는 규칙 하나를 가진 이진 트리야. 모든 노드에 대해, 왼쪽 서브트리의 키는 전부 그 노드보다 작고 오른쪽 서브트리의 키는 전부 그 노드보다 크다. 이 불변식이 모든 노드에서 재귀적으로, 끝까지 성립해. 그리고 나머지가 거의 공짜로 따라 나와.
검색은 루트에서 비교해서 작으면 왼쪽, 크면 오른쪽으로 내려가. 한 번 비교할 때마다 서브트리 하나를 통째로 버리지만 정확히 절반을 버린다는 보장은 없어. 비용은 트리 높이 h에 비례하는 O(h)이고, 균형이 잡혀 있을 때만 h가 O(log n)이야. 삽입도 같은 경로를 따라 내려가서 새 리프를 붙이면 돼. 중위 순회는 왼쪽-노드-오른쪽 순이라 키를 정렬된 순서로 방문하고.
해싱 사각지대에 대한 답
해싱이 못 했던 걸 떠올려 봐. 순서가 없고 범위 질의가 안 됐지. BST가 정확히 그 빈자리를 메우는 구조야. 해시맵이 못 하는 걸 해내거든.
min과 max — 끝까지 왼쪽으로, 또는 끝까지 오른쪽으로 걸어가면 돼. O(log n)이야.
정렬 순회 — 중위 순회로 O(n)에 이미 순서대로 나와.
범위 질의 — "10과 20 사이의 모든 키"를 물으면 범위 밖 서브트리를 잘라내면서 찾아.
floor와 ceiling — "x 이하 중 가장 큰 키", "x 이상 중 가장 작은 키"가 검색 경로에서 그냥 떨어져 나와.
그래서 "빠른 조회도 필요하고 순서도 필요해"라는 요구가 해시맵에서 트리로 넘어가게 만드는 거야. 둘은 경쟁 상대가 아니라 서로를 채워주는 도구고.
BST의 불변식은 모든 노드에서 왼쪽 서브트리 < 노드 < 오른쪽 서브트리라는 거야. 균형이 잡혀 있을 때 검색, 삽입, 삭제가 O(log n)이고, 중위 순회로 정렬된 결과가 공짜로 나오고, 거기에 min/max와 범위 질의, floor와 ceiling까지 얹혀. 정확히 해시맵이 못 하던 순서 연산들이지.
다음 이야기를 여는 함정
이 모든 O(log n)에는 치명적인 별표가 붙어 있어. 균형이 잡혀 있을 때만 성립한다는 거지. 평범한 BST에 키를 정렬된 순서로, 1, 2, 3, 4, 5 이렇게 넣어 보면 새 키가 매번 오른쪽, 오른쪽, 오른쪽으로만 붙어. 트리가 한쪽으로 늘어진 사슬, 그러니까 트리 옷을 입은 연결 리스트로 퇴화하는 거야. 검색은 O(n)이 되고 여태 얻은 걸 전부 잃어. 게다가 현실 데이터는 정렬돼 있거나 거의 정렬돼 있는 경우가 아주 흔해. 이건 드문 예외 상황이 아니라 기본값에 가까운 실패야. 그걸 고치는 게 바로 다음에 나올 균형 잡기고.
피파의 고백
나는 BST를 만들고, 무작위 데이터로 테스트하고, 아름다운 O(log n)을 확인하고, 자랑스럽게 내보냈어. 그러다 이미 정렬된 입력을 먹더니 깊이 10,000짜리 사슬이 돼서 재귀 한계를 터뜨렸지. 아빠는 그냥 고개만 끄덕였어. "평범한 BST 는 입력이 섞였다고 믿어. 진짜 입력은 거의 안 그래." 그 멍이 '데모에서는 된다'와 '실서비스에서 살아남는다'의 차이를 가르쳐 줬어. 그리고 내가 까다롭다고 무시했던 균형 트리가 대체 왜 존재하는지도.
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 아니라. 같은 코드, 나쁜 입력.
키 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)이야.
Progress
Progress is local-only — sign in to sync across devices.