왼쪽 자식은 나보다 작고, 오른쪽 자식은 나보다 크다는 규칙을 모든 노드가 지키는 이진 트리(BST, Binary Search Tree). "이진"은 자식이 최대 2개라는 뜻이다.
왜 빠른가 — 절반씩 버린다
찾는 값이 현재 노드보다 작으면 오른쪽 전체를 볼 필요가 없다. 한 번 비교할 때마다 후보가 절반으로 줄어든다.
8
/ 3 10 7을 찾는다면
/ \ \ 7 < 8 → 왼쪽으로 (10 이하 가지 전부 제외)
1 6 14 7 > 3 → 오른쪽으로 (1 제외)
/ \ 7 > 6 → 오른쪽 → 찾음
4 7
n개를 절반씩 나누면 log₂n번 만에 1개가 남는다. 그래서 균형이 잡혀 있으면 O(log n)이다.
(n=1,000,000이어도 20번이면 찾는다.)
퇴화 — BST의 근본 약점
정렬된 데이터를 순서대로 넣으면 한쪽으로만 자란다.
1 → 2 → 3 → 4 → 5 를 차례로 삽입하면
1
- 2
- 3
- 4
사실상 연결 리스트가 되어 탐색이 O(n)으로 무너진다.
이것이 자가 균형 트리가 등장한 이유다.
자가 균형 트리
삽입·삭제할 때마다 회전(rotation) 으로 모양을 바로잡아 높이를 log n으로 유지한다.
| 종류 | 균형 기준 | 성격 |
|---|---|---|
| AVL | 좌우 높이 차 ≤ 1 (엄격) | 회전이 잦다 → 조회에 유리 |
| 레드-블랙 | 색 규칙으로 느슨하게 | 회전이 적다 → 삽입·삭제에 유리 |
| B/B+트리 | 노드 하나에 키 여러 개 | 디스크 I/O 최소화 → DB 인덱스 |
자바 TreeMap·TreeSet이 레드-블랙 트리다.
B+트리가 DB 인덱스인 이유
디스크는 한 번 읽을 때 블록 단위로 가져온다. 이진 트리는 노드마다 자식이 2개라 높이가 높고, 높이만큼 디스크를 읽어야 한다.
B+트리는 노드 하나에 키를 수백 개 담아 자식이 수백 개다. 그래서 100만 건이어도 높이가 3~4면 충분하다 — 디스크 접근이 3~4번으로 끝난다.
해시 테이블과 비교 — 면접 단골
| 해시 테이블 | 균형 BST | |
|---|---|---|
| 단일 키 조회 | O(1) 평균 | O(log n) |
| 정렬 순서 | 없음 | 유지됨 |
범위 조회 (10~20 사이) | 불가 — 전체 훑어야 함 | O(log n + k) |
| 최솟값·최댓값 | 전체 훑기 | 맨 왼쪽·오른쪽 |
"정렬이나 범위 조회가 필요하면 트리, 단순 키 조회면 해시" 가 답변의 뼈대다.
DB 인덱스가 해시가 아니라 B+트리인 이유도 BETWEEN·ORDER BY 때문이다.