
이진 탐색 트리(BST): 데이터 검색의 기초와 자가 균형의 미학
업다운 게임으로 배우는 이진 탐색 트리. 왜 데이터베이스는 해시 테이블 대신 B-Tree를 쓸까? AVL 트리, 레드블랙 트리, 그리고 Splay Tree까지.

업다운 게임으로 배우는 이진 탐색 트리. 왜 데이터베이스는 해시 테이블 대신 B-Tree를 쓸까? AVL 트리, 레드블랙 트리, 그리고 Splay Tree까지.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.

친구와 1부터 100 사이 숫자를 맞추는 게임을 한다고 상상해 봅시다. 정답은 70입니다.
가장 단순무식한 방법은 1부터 차례대로 물어보는 것입니다. "1이야?" "아니." "2야?" "아니." ... "69야?" "아니." "70이야?" "정답!" 최악의 경우 100번을 물어봐야 합니다. 시간 복잡도는 O(N)입니다. 데이터가 100만 개라면 100만 번 확인해야 합니다. 만약 데이터베이스가 이렇다면 여러분은 로그인 한번 할 때마다 1분씩 기다려야 할 겁니다.
가운데를 찌릅니다.
이렇게 한 번 물어볼 때마다 범위를 절반씩 줄여나가면, 100개의 데이터도 단 7번 만에 맞출 수 있습니다 ($2^7 = 128$). 100만 개의 데이터도 20번이면 찾습니다 ($2^ \approx 1,000,000$). 이 시간 복잡도는 O(log N)입니다. 이 전략을 그대로 데이터 구조로 구현한 것이 바로 이진 탐색 트리(BST)입니다.
이진 탐색 트리는 다음 규칙을 엄격하게 지키는 트리입니다.
이 규칙 덕분에 검색 로직이 단순해집니다. "찾는 값이 현재 노드(70)보다 작네(50)? 그럼 오른쪽은 볼 필요도 없어. 왼쪽으로 가!" 한 번 움직일 때마다 검색 대상이 절반으로 줄어듭니다.
class Node:
def __init__(self, key):
self.val = key
self.left = None
self.right = None
def search(root, key):
# Base Case: 못 찾았거나, 찾았거나
if root is None or root.val == key:
return root
# 찾는 값이 현재보다 작으면 왼쪽으로
if key < root.val:
return search(root.left, key)
# 크면 오른쪽으로
return search(root.right, key)
재귀(Recursion)를 사용하면 코드가 매우 직관적입니다. 시간 복잡도: $O(h)$ (트리의 높이).
검색과 똑같이 따라가다가, Null(없는 곳)을 만나면 거기에 새 노드를 집어넣습니다.
이미 있는 값이면? 무시하거나 에러를 내거나 카운트를 증가시킵니다.
노드를 지울 때는 신중해야 합니다. 자식들이 미아가 되면 안 되니까요. 세 가지 케이스를 다뤄야 합니다.
Null로 바꿉니다.def delete_node(root, key):
if not root: return root
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else:
# 찾았다! 지우자.
if not root.left: return root.right # 자식 하나 or 0
if not root.right: return root.left
# 자식 둘: Successor 찾기
temp = find_min(root.right)
root.val = temp.val
root.right = delete_node(root.right, temp.val)
return root
많은 교과서가 재귀로 BST를 설명하지만, 실제나 성능이 중요한 환경에서는 반복문(Iterative)을 선호합니다. 재귀는 함수 호출 오버헤드와 스택 메모리를 소모하기 때문입니다.
Iterative Search 예시 (Python)def search_iterative(root, key):
current = root
while current:
if key == current.val:
return current
elif key < current.val:
current = current.left
else:
current = current.right
return None
이 방식은 공간 복잡도가 O(1)입니다. 재귀는 O(h)죠. 트리 높이가 10만이라도 스택 오버플로우 걱정이 없습니다. 실무에서 "재귀 말고 반복문으로 짜보세요"라는 요청이 나오면 바로 이렇게 전환할 수 있어야 합니다.
둘 다 이진 트리 형태지만 목적과 규칙이 완전히 다릅니다.
| 특징 | BST (이진 탐색 트리) | Heap (힙) |
|---|---|---|
| 목적 | 검색 (Search) | 최댓값/최솟값 빠르게 찾기 |
| 규칙 | 왼쪽 < 부모 < 오른쪽 | 부모 > 자식 (Max Heap) |
| 정렬 | 중위 순회 시 정렬됨 | 정렬 안 됨 (느슨한 정렬) |
| 검색 시간 | O(log N) | O(N) (랜덤 검색 시) |
| 삽입/삭제 | O(log N) | O(log N) |
| 사용처 | DB 인덱스, Map/Set | 우선순위 큐 (Priority Queue) |
"우선순위 큐를 구현할 때 BST를 써도 되나요?" 가능은 하지만 비효율적입니다. 힙은 배열(Array)로 구현 가능해서 메모리 효율과 캐시 지역성(Cache Locality)이 훨씬 뛰어난 반면, BST는 포인터 기반이라 오버헤드가 큽니다.
만약 데이터가 정렬된 상태로 1, 2, 3, 4, 5 순서대로 들어오면 어떻게 될까요?
결과적으로 트리가 아니라 그냥 오른쪽으로 기울어진 막대기(Linked List)가 되어버립니다. 이 모양을 편향 트리(Skewed Tree)라고 합니다. 이때의 트리 높이 $h$는 $N$이 됩니다. 검색 시간 복잡도는 O(N)으로 퇴화합니다. 비싼 스포츠카(BST)를 샀는데 자전거(Linked List) 속도가 나오는 셈입니다.
데이터가 입력될 때마다 트리의 회전(Rotation)을 수행하여 높이를 낮게 유지하는 알고리즘들이 있습니다.
TreeMap, C++의 std::map이 내부적으로 이걸 씁니다. 실제 표준입니다.리눅스는 운영체제입니다. 수천 개의 프로세스가 메모리를 달라고 아우성칩니다. 각 프로세스가 사용하는 메모리 영역(VMA, Virtual Memory Area)을 관리해야 하는데, 이 VMA 리스트를 어떻게 저장할까요?
mm_struct 안에는 vm_area_struct를 관리하는 Red-Black Tree가 들어있습니다.
여러분이 지금 브라우저를 띄우고 유튜브를 보는 것도, 결국 이 이진 탐색 트리가 메모리를 효율적으로 관리해주기 때문에 가능한 일입니다.트리의 모든 노드를 빠짐없이 방문하는 방법입니다.
Root -> Left -> Right (트리 복사용)Left -> Root -> Right (정렬된 결과)Left -> Right -> Root (트리 삭제용)순회 코드를 짤 때 보통 재귀(Recursion)를 씁니다.
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)
하지만 트리가 매우 깊다면? (Depth > 10,000).
Stack Overflow가 발생합니다.
실제로는 이를 방지하기 위해 Morris Traversal (Link를 임시으로 수정해서 스택 없이 순회)이나 Threaded Binary Tree를 사용하기도 합니다.
Threaded Binary Tree는 Null 포인터를 낭비하지 않고, 다음 방문할 노드(Successor)를 가리키게 하여 재귀 없이 순회할 수 있게 만든 최적화된 자료구조입니다.
임베디드 시스템처럼 메모리가 귀한 곳에서 쓰입니다.
일반적인 BST가 지루한 당신을 위한 고급 자료구조입니다.
"한 번 찾은 놈은 또 찾을 확률이 높다" (Temporal Locality)는 원리를 이용합니다. 어떤 노드를 검색하거나 삽입하면, 그 노드를 회전(Rotation)을 통해 루트(Root)까지 끌어올립니다. 이렇게 하면 자주 찾는 데이터는 루트 근처에 모이게 됩니다. 캐시(Cache) 구현에 아주 유용합니다. 균형을 완벽하게 맞추진 않지만, 실제적으로 매우 빠릅니다.
BST의 규칙(왼쪽 < 부모 < 오른쪽)과, 힙(Heap)의 규칙(부모 우선순위 > 자식 우선순위)을 섞은 것입니다. 각 노드에 랜덤한 '우선순위'를 부여합니다. 이렇게 하면 데이터가 정렬된 순서로 들어와도, 우선순위가 랜덤하기 때문에 트리가 확률적으로 균형 잡힌 모양을 갖게 됩니다. 구현이 쉽고 성능이 좋습니다.
해시는 빠릅니다. 하지만 순서가 없습니다.
정확히는 BST의 사촌인 B-Tree (또는 B+Tree)를 씁니다.
A: 해시 테이블은 검색 속도가 O(1)로 빠르지만, 순서가 없습니다. 그래서 "10보다 크고 20보다 작은 값" 같은 범위 검색(Range Query)을 할 수 없습니다. 반면 BST는 중위 순회(In-order)를 하면 정렬된 데이터를 얻을 수 있어 범위 검색에 유리합니다.
A: AVL 트리는 균형을 너무 엄격하게(높이 차 1 이하) 맞추느라, 데이터 삽입/삭제 때마다 회전 연산을 너무 많이 합니다. 반면 Red-Black 트리는 균형 조건을 약간 느슨하게 해서 회전 횟수를 줄였습니다. 검색 속도는 AVL보다 아주 약간 느리지만, 삽입/삭제 성능이 훨씬 좋아서 범용적인 라이브러리(Java TreeMap, C++ Map, Linux Scheduler)에 채택되었습니다.
A: 디스크 I/O 때문입니다. 일반 BST는 노드 하나가 메모리 여기저기에 흩어져 있지만, B-Tree는 하나의 노드(페이지)에 수백 개의 키를 꽉 채워 넣습니다. 디스크에서 한 블록(4KB)을 읽어오면 수백 개의 자식 주소를 한 번에 알 수 있어, 트리의 높이가 매우 낮아집니다. 디스크 접근 횟수를 최소화하기 위해 설계된 트리입니다.
이진 탐색 트리는 우리에게 "균형(Balance)"의 중요성을 가르쳐 줍니다. 한쪽으로 치우친 편향 트리는 데이터가 쌓일수록 느려지고 무능해집니다. 반면 스스로 균형을 맞추는 AVL이나 Red-Black 트리는 어떤 시련(데이터 폭주)이 와도 $O(\log N)$의 평정심을 유지합니다.
개발자로서의 삶도 마찬가지 아닐까요? 특정 기술 하나에만 너무 깊게 파고들면(Over-fitting), 기술 트렌드가 바뀌었을 때 적응하기 힘듭니다. 반대로 너무 얕게만 알면 깊이 있는 문제를 해결하지 못합니다. 이론(CS)과 실무(Engineering) 사이의 균형, 일과 삶의 균형(Work-Life Balance). BST가 스스로 회전하며 늘 중심을 잡듯이, 우리도 끊임없이 Self-Balancing을 해야 롱런하는 개발자가 될 수 있지 않을까 생각합니다.
Guess a number between 1 and 100. Target is 70.
The Dumb Strategy (O(N)) "Is it 1?" "No." "Is it 2?" "No." ... "Is it 70?" "Yes!" If the range is 1 million, you might ask 1 million questions. This is Linear Search.
The Smart Strategy (O(log N)) "Is it bigger than 50?" "Yes." (Eliminated 1-50. 50 candidates left.) "Is it bigger than 75?" "No." (Eliminated 76-100. 25 candidates left.) "Is it bigger than 62?" ... By cutting the search space in half every time, you can find the answer in just 7 steps ($2^7 = 128$). Even with 1 Billion items, it takes only 30 steps ($2^ \approx 10^9$). The Binary Search Tree is the data structure that embodies this strategy.
A BST is a tree that strictly follows these rules:
Because of these rules, you act like a traffic controller: "Target 70? You are bigger than me (50). Go Right. Do not verify Left."
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
def search(root, key):
# Base Case: Found or Empty
if root is None or root.val == key:
return root
# Target is smaller? Go Left.
if key < root.val:
return search(root.left, key)
# Target is bigger? Go Right.
return search(root.right, key)
Recursive logic makes BST algorithms clean and elegant. Time Complexity is $O(h)$ where $h$ is the height of the tree.
Follow the search path. When you hit a Dead End (None), plant the new node there.
It naturally finds its correct sorted position.
Note: You don't need to move other nodes like in an Array. just change one pointer. This is why insertion is also $O(\log N)$, unlike Array's $O(N)$.
Removing a node has 3 scenarios:
What happens if you insert sorted data: 1, 2, 3, 4, 5?
The height $h$ becomes $N$. Search time degrades to O(N). You paid for a sports car (BST) but got a bicycle (Linked List).
We need algorithms that automatically rearrange (Rotate) the tree to keep it bushy, not deep.
How do we walk through every node?
1, 5, 10, 15...10, 5, 1, 15...1, 5, 15, 10...Hash Tables are fast but Unordered.
A Standard BST stores nodes randomly in memory. Disk drives read data in Blocks (or Pages, e.g., 4KB, 8KB, 16KB).
In a normal BST implementation, leaf nodes have null pointers for left/right.
Functionally, about 50% of pointers in a tree are null. That's wasted memory space.
Threaded Binary Trees use these null pointers to point to the In-order Predecessor or Successor.
Uses the principle of Temporal Locality: "If I accessed it now, I'll likely access it again soon." Whenever you search/insert a node, you Splay (Rotate) it all the way to the Root. Frequently accessed hot nodes stay near the top. Very efficient for Cache implementation, even without strict balancing.
Tree + Heap.
Each node has a Key (for BST requirement) and a Random Priority (for Heap requirement).
Hash Tables are $O(1)$ but unordered. If you need Range Queries ("Find users between age 20 and 30") or Nearest Neighbor searches, Hash Tables fail. BSTs excel at this.
Java TreeMap work?It uses a Red-Black Tree.
It guarantees $O(\log N)$ for containsKey, get, put, and remove.
It also provides methods like floorKey(K key) (greatest key less than or equal to K) which simple HashMaps cannot do.
If you insert N items one by one: