이진 탐색 트리: 작은 것은 왼쪽, 큰 것은 오른쪽
값을 노드에 담아 트리 모양으로 매답니다. 노드마다 지키는 규칙은 하나입니다: 왼쪽 아래는 모두 나보다 작고, 오른쪽 아래는 모두 나보다 큽니다. 그러면 무엇을 찾든 루트에서부터 「작으면 왼쪽, 크면 오른쪽」만 따라 내려가면 됩니다.
한 줄 답. 이진 탐색 트리는 노드마다 왼쪽 서브트리는 모두 작고 오른쪽 서브트리는 모두 크다는 규칙을 지키는 트리입니다. 찾기·넣기·지우기는 루트에서 비교하며 한 층씩 내려가므로 트리의 높이(height, 층 수)만큼 걸립니다. 뒤섞인 순서로 넣으면 높이가 log n 에 가까워 빠르지만, 정렬된 순서로 넣으면 한 줄로 늘어져(치우친 트리, degenerate tree) 리스트처럼 n 번 걸립니다. 중위 순회(in-order traversal), 곧 왼쪽-나-오른쪽 순서로 읽으면 값이 정렬되어 나와서, 범위로 찾기(범위 질의, range query)와 순서대로 꺼내기를 잘합니다.
그림 읽기: 주황과 「지금」 화살표 = 지금 노드 · 굵은 주황 화살표와 기호(5 < 8) = 비교한 뒤 내려갈 쪽 · 옅은 초록 = 지나온 길 · 초록 = 찾음 · 파랑 = 새 노드 · 파란 점선 = 새 노드가 붙을 빈자리 · 주황 점선 = 지울 노드 · 보라 = 오른쪽 최솟값 · 보라 화살표 = 값이 옮겨 감 · 흐린 점선 = 값이 떠난 노드
값(0 ~ 99 의 정수)을 적고 단추를 누르면 걸음 목록이 만들어지고, 「다음」으로 한 걸음씩 따라갑니다. 트리는 단추를 누를 때 이미 끝 결과로 바뀌어, 다음 단추는 바뀐 트리에서 시작합니다. 처음 트리는 8, 3, 10, 1, 6, 14, 4, 7 을 이 순서로 넣은 것이고 2절의 손 예제와 같습니다. 값은 20개까지 넣습니다.
해 볼 것. ① 5 로 「찾기」: 8, 3, 6, 4 와 비교하고 4 의 오른쪽이 비어 있어 없다고 끝납니다(비교 횟수 4). ② 그대로 「넣기」: 같은 네 번을 비교한 뒤 그 빈자리(4 의 오른쪽)에 5 가 붙습니다. 찾다가 멈춘 곳이 곧 넣을 곳입니다. ③ 「처음 트리」에서 1 을 지우면 리프라 떼기만 합니다(5걸음). 10 을 지우면 자식 14 가 올라옵니다(4걸음). 3 을 지우면 자식이 둘이라 오른쪽 자식 6 에서 왼쪽 끝 4 까지 내려가 4 를 고르고, 4 를 3 의 자리로 옮긴 뒤(보라 화살표) 4 가 떠난 노드를 뗍니다(7걸음). 어느 경우든 아래 줄의 왼쪽-나-오른쪽 순서는 정렬된 채입니다.
1. 규칙: 왼쪽은 모두 작고, 오른쪽은 모두 크다
트리의 노드(node) 하나에는 값 하나와 자식을 가리키는 간선 둘(왼쪽, 오른쪽)이 있습니다. 맨 위 노드를 루트(root), 자식이 없는 노드를 리프(leaf), 어떤 노드와 그 아래 전부를 그 노드의 서브트리(subtree)라고 부르겠습니다. 이진 탐색 트리는 모든 노드가 아래 규칙을 지킵니다.
왼쪽 서브트리의 값 < 나 < 오른쪽 서브트리의 값 (모든 노드에서)
「왼쪽 자식이 나보다 작다」가 아니라 왼쪽 서브트리 전부가 작다는 점이 중요합니다. 그래서 어느 노드에서 오른쪽으로 내려가면, 그 뒤로 만나는 값은 모두 그 노드보다 큽니다. 비교할 때마다 남은 후보의 한쪽을 통째로 버릴 수 있는 까닭입니다. 이진 탐색이 정렬된 배열의 가운데와 비교하며 반씩 버리는 것과 같은 생각을, 배열 대신 간선으로 이은 노드에 담은 것입니다.
| 성질 | 쉬운 말 | 실험에서 |
|---|---|---|
| 찾기·넣기·지우기는 높이만큼 | 한 번 비교할 때 한 층 내려간다. 걸음 수는 많아야 트리의 층 수다 | ① 의 걸음 수 |
| 찾다가 멈춘 곳이 넣을 곳 | 없는 값을 찾으면 빈자리에서 멈추고, 넣기는 그 빈자리에 새 노드를 단다. 다른 노드는 움직이지 않는다 | ① 해 볼 것 ①·② |
| 왼쪽-나-오른쪽으로 읽으면 정렬된 줄 | 규칙이 지켜지는 한 늘 작은 것부터 나온다 | ① 의 아래 줄 |
| 모양은 넣는 순서가 정한다 | 같은 값이라도 순서가 다르면 높이가 다르다. 정렬된 순서면 한 줄이 된다 | ② 의 두 단추 |
| 가장 작은 값은 왼쪽 끝 | 루트에서 왼쪽으로만 내려가 더 갈 곳이 없는 노드. 가장 큰 값은 오른쪽 끝 | 지우기의 자식 둘 경우 |
2. 손으로 따라가기
빈 트리에 8, 3, 10, 1, 6, 14, 4, 7 을 이 순서로 넣습니다. 값마다 루트에서 출발해 작으면 왼쪽, 크면 오른쪽으로 가다가 빈자리를 만나면 거기에 답니다.
| 넣는 값 | 비교하는 길(작으면 왼쪽, 크면 오른쪽) | 다는 곳(처음 만난 빈자리) |
|---|---|---|
| 8 | (빈 트리) | 루트 |
| 3 | 3 < 8 → 왼쪽 | 8 의 왼쪽 |
| 10 | 10 > 8 → 오른쪽 | 8 의 오른쪽 |
| 1 | 1 < 8 → 왼쪽, 1 < 3 → 왼쪽 | 3 의 왼쪽 |
| 6 | 6 < 8 → 왼쪽, 6 > 3 → 오른쪽 | 3 의 오른쪽 |
| 14 | 14 > 8 → 오른쪽, 14 > 10 → 오른쪽 | 10 의 오른쪽 |
| 4 | 4 < 8 → 왼쪽, 4 > 3 → 오른쪽, 4 < 6 → 왼쪽 | 6 의 왼쪽 |
| 7 | 7 < 8 → 왼쪽, 7 > 3 → 오른쪽, 7 > 6 → 오른쪽 | 6 의 오른쪽 |
다 넣으면 4층짜리 트리가 됩니다. 1층에 8, 2층에 3 과 10, 3층에 1, 6, 14, 4층에 4 와 7 입니다.
- 7 찾기. 8(작다, 왼쪽) → 3(크다, 오른쪽) → 6(크다, 오른쪽) → 7(같다). 4번 비교해 찾습니다.
- 5 찾기. 8 → 3 → 6(작다, 왼쪽) → 4(크다, 오른쪽) → 빈자리. 4번 비교하고 없다고 답합니다. 여기에 5 를 넣으면 바로 이 빈자리에 붙습니다.
- 지우기 세 경우. 리프 1 은 그냥 뗍니다. 자식이 하나인 10 은 그 자식 14 를 10 의 자리로 올립니다. 자식이 둘인 3 은 빈자리를 남기면 두 서브트리를 한 줄에 달 수 없으니, 오른쪽 서브트리에서 가장 작은 값, 곧 후계자(successor)를 찾습니다. 오른쪽 자식 6 에서 왼쪽으로 끝까지 가면 4 입니다. 4 는 3 보다 크고 6, 7 보다 작아 3 의 자리에 놓아도 규칙이 지켜집니다. 4 의 원래 노드는 왼쪽 자식이 없으니 리프나 자식 하나의 경우로 쉽게 뗍니다.
값마다 찾는 데 비교하는 횟수는 그 값이 있는 층의 번호, 곧 깊이(depth)와 같습니다. 이 트리에서 여덟 값의 평균은 (1×1 + 2×2 + 3×3 + 4×2) ÷ 8 = 22 ÷ 8 = 2.75 번입니다.
3. 중위 순회: 왼쪽-나-오른쪽으로 돌면 정렬된 줄이 나온다
노드마다 「왼쪽 서브트리를 다 읽고 → 나를 읽고 → 오른쪽 서브트리를 다 읽는」 순서로 트리 전체를 돕니다(중위 순회). 규칙에 따라 왼쪽 서브트리는 모두 나보다 작고 오른쪽 서브트리는 모두 크니, 나는 늘 작은 것들 바로 뒤, 큰 것들 바로 앞에 나옵니다. 서브트리 안에서도 같은 일이 되풀이되므로 전체가 작은 것부터 늘어섭니다. 2절의 트리는 1, 3, 4, 6, 7, 8, 10, 14 로 읽힙니다.
이 성질 덕분에 「가장 작은 것」, 「7 바로 다음 값」, 「4 이상 9 이하의 값 모두」 같은 질문을 잘 풉니다. 범위의 시작을 찾는 데 높이만큼, 그다음은 꺼내는 개수만큼 걸립니다. 키가 섞여 저장되는 해시 테이블은 이런 질문에 답하려면 전부 꺼내 정렬해야 합니다.
4. 찾기·넣기·지우기는 트리 높이만큼 걸린다
세 일 모두 루트에서 비교하며 한 층씩 내려가고, 지우기의 자식 둘 경우도 더 아래로 내려갈 뿐입니다. 그래서 걸리는 시간은 트리의 높이(층 수)에 비례합니다. 같은 값 n 개라도 높이는 크게 다를 수 있습니다.
| 값의 수 n | 가장 낮게 세우면(층마다 1, 2, 4, … 개) | 한 줄로 늘어지면(치우친 트리) |
|---|---|---|
| 15 | 4층 | 15층 |
| 1,000,000 | 20층(2²⁰ = 1,048,576 이라 20층에 다 들어간다) | 1,000,000층 |
가장 낮은 높이는 log₂(n + 1) 을 올린 값입니다. n 이 두 배가 되면 한 층 늘 뿐입니다(O(log n)). 한 줄이면 n 이 두 배일 때 걸음도 두 배입니다(O(n)). 출처는 뒤섞인 순서로 넣은 트리라면 찾는 데 드는 평균 걸음이 log n 에 비례한다고 보입니다. 아래 실험에서 순서만 바꿔 보세요.
값은 1 부터 n 까지(7 ~ 15개)입니다. 「뒤섞어 넣기」는 고정 씨앗 난수기로 섞어 쪽을 열 때마다 같은 순서입니다. 평균 찾는 걸음은 트리에 있는 값을 하나씩 찾을 때 비교하는 횟수의 평균입니다.
해 볼 것. ① 처음(15개, 뒤섞기)은 높이 6층, 평균 찾는 걸음 3.87번입니다. 가장 낮은 4층보다 조금 높습니다(4층으로 꽉 채우면 평균 49 ÷ 15 ≈ 3.27). ② 「작은 것부터 차례로 넣기」를 누르면 모든 값이 바로 앞 값의 오른쪽에 붙어 15층, 평균 8번이 됩니다. 맨 끝 값 15 를 찾으려면 15번 비교합니다. 리스트를 처음부터 훑는 것과 같습니다. ③ 값의 수를 7 로 두면 뒤섞기는 3층(가장 낮은 높이), 평균 2.43번이고 차례로는 7층, 평균 4번입니다. ④ 11 로 두면 뒤섞기도 8층으로 높습니다. 뒤섞으면 보통 낮지만 늘 그렇지는 않습니다.
모양을 운에 맡기지 않으려면 넣고 지울 때마다 노드를 돌려 높이를 log n 쯤으로 지키는 균형 잡힌 트리를 씁니다. 다음 쪽 레드-블랙 트리가 그 방법입니다.
5. 언제 무엇을 쓰나
O(1) 은 n 과 상관없이 몇 번, O(log n) 은 n 이 두 배면 한 번 더, O(n) 은 n 이 두 배면 두 배, O(n log n) 은 그보다 조금 더입니다. n 은 저장한 값의 수, k 는 꺼내는 값의 수입니다.
| 선택지 | 찾기(좋을 때 · 보통 · 나쁠 때) | 넣기 · 지우기 | 범위 질의 · 순서대로 꺼내기 | 더 드는 메모리 | 쓰는 경우 |
|---|---|---|---|---|---|
| 이진 탐색 트리(이 쪽) | O(1) 루트에 있을 때 · O(log n) 뒤섞인 순서로 넣었을 때 · O(n) 한 줄일 때 | 찾기와 같다 | 잘한다. O(높이 + k) | 값마다 자식 줄 둘 | 배울 때. 넣는 순서가 뒤섞여 있다고 믿을 수 있을 때 |
| 균형 잡힌 트리 | O(1) · O(log n) · O(log n) | O(log n), 나쁠 때도 | 잘한다. O(log n + k) | 줄 둘에 노드마다 색 표시 하나 | 순서가 필요한 사전을 오래 바꿔 가며 쓸 때 |
| 해시 테이블 | O(1) · O(1) · O(n) 모두 한 칸에 몰릴 때 | 보통 O(1) | 못한다. 다 꺼내 정렬해야 한다 O(n log n) | 비워 둔 칸이 있는 표 | 정확한 키로만 찾을 때 |
| 정렬된 배열 + 이진 탐색 | O(1) · O(log n) · O(log n) | O(n). 뒤의 값을 한 칸씩 민다 | 잘한다. O(log n + k) | 없다 | 한 번 만들고 거의 바꾸지 않을 때 |
6. 진짜 코드
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(node, key): # 넣은 뒤의 루트를 돌려준다
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
return node
def inorder(node): # 중위 순회: 왼쪽-나-오른쪽
return inorder(node.left) + [node.key] + inorder(node.right) if node else []
root = None
for key in [8, 3, 10, 1, 6, 14, 4, 7]:
root = insert(root, key)
print(inorder(root)) # [1, 3, 4, 6, 7, 8, 10, 14]
파이썬 표준 라이브러리에는 이 트리가 없습니다. 비슷한 일은 정렬된 리스트와 bisect 로 합니다: bisect.insort(values, 5). 찾기는 O(log n) 이지만 넣기는 뒤의 값을 미느라 O(n) 입니다(위 표의 넷째 줄).
어디에 쓰나
- 순서가 필요한 사전. 키로 찾으면서 「가장 작은 것」, 「이 값 바로 다음」, 「a 와 b 사이 모두」를 자주 물을 때. 실제로는 균형 잡힌 트리를 씁니다.
- 균형 잡힌 트리의 바탕. 레드-블랙 트리는 이 규칙과 찾기를 그대로 쓰고, 넣고 지울 때 모양을 맞추는 일만 더합니다.
- 데이터베이스 인덱스를 이해하는 첫걸음. 인덱스가 쓰는 B-트리는 한 노드에 키를 여러 개 두고 갈래를 여러 개로 넓힌 트리로, 「작은 쪽, 큰 쪽으로 갈라 내려간다」는 생각이 같습니다.
자주 묻는 것
같은 값을 두 번 넣으면 어떻게 되나요?
정하기 나름입니다. 이 쪽의 실험은 같은 값이 오면 아무것도 하지 않습니다. 출처의 구현은 키와 값을 짝으로 두는 사전이라, 같은 키가 오면 노드를 새로 만들지 않고 값만 바꿉니다. 같은 값을 여러 개 두려면 「같으면 오른쪽」처럼 한쪽으로 정하거나, 노드에 개수를 적어 둡니다.
지울 때 왼쪽 서브트리의 가장 큰 값으로 바꿔도 되나요?
됩니다. 왼쪽 서브트리의 가장 큰 값은 지울 노드보다 작은 값 가운데 가장 크므로, 그 자리에 놓아도 왼쪽은 모두 작고 오른쪽은 모두 크다는 규칙이 지켜집니다. 이 쪽과 출처는 오른쪽 서브트리의 가장 작은 값을 씁니다.
왜 실무에서는 이 트리를 그대로 잘 쓰지 않나요?
넣는 순서에 따라 한 줄로 늘어질 수 있기 때문입니다. 차례로 늘어나는 번호처럼 이미 정렬된 순서로 들어오면 찾기가 리스트처럼 n 번 걸립니다. 그래서 넣고 지울 때마다 모양을 다시 맞춰 높이를 log n 쯤으로 지키는 균형 잡힌 트리(레드-블랙 트리 등)를 씁니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 작은 것은 왼쪽, 큰 것은 오른쪽인 트리 | 이진 탐색 트리(binary search tree, BST) |
| 값 하나를 담는 동그라미 | 노드(node) |
| 맨 위 노드 · 자식이 없는 노드 | 루트(root) · 리프(leaf) |
| 어떤 노드와 그 아래 전부 | 서브트리(subtree) |
| 층 수 · 몇 층에 있나 | 높이(height) · 깊이(depth). 책에 따라 층 수가 아니라 간선 수로 세어 1 작게 적기도 한다 |
| 비교하기 | 비교(compare) |
| 왼쪽-나-오른쪽 순서로 돌기 | 중위 순회(in-order traversal) |
| 오른쪽 서브트리의 가장 작은 값 | 후계자(successor) |
| 자식 둘인 노드를 후계자로 바꿔 지우기 | 히바드 삭제(Hibbard deletion) |
| 범위로 찾기 | 범위 질의(range search, range query) |
| 한 줄로 늘어진 트리 | 치우친 트리, 퇴화 트리(degenerate tree) |
| 높이를 log n 쯤으로 지키는 트리 | 균형 이진 탐색 트리(balanced BST) |
출처
- Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, 3.2 Binary Search Trees. 규칙, 찾기와 넣기, 순서로 하는 일(가장 작은 값, 범위), 후계자로 바꾸는 지우기, 넣는 순서와 모양.