최적 이진 탐색 트리 계산기
키마다의 탐색 빈도를 넣으면 기대 탐색 비용이 가장 작은 이진 탐색 트리를 구간 DP로 만듭니다. 빈도 순 그리디·균형 트리와 비용을 나란히 놓아 왜 자주 찾는 키를 무조건 위로 올리면 안 되는지 보여 줍니다.
한 줄에 «키 빈도». 빈도를 안 적으면 1로 봅니다. 넣은 순서와 상관없이 정렬해서 다룹니다
최적 트리의 기대 탐색 비용
108 (평균 1.049번 비교)
키 4개 · 빈도 합 103 · 뿌리는 a
최적 (구간 DP) — 기대 비용 108 · 평균 1.049번 비교 · 높이 3
a · 100 └오 c · 1 ├왼 b · 1 └오 d · 1
빈도 순 그리디 — 기대 비용 109 · 평균 1.058번 비교 · 높이 4
a · 100
└오 b · 1
└오 c · 1
└오 d · 1균형 (가운데를 뿌리로) — 기대 비용 206 · 평균 2번 비교 · 높이 3
b · 1 ├왼 a · 100 └오 c · 1 └오 d · 1
키마다의 깊이와 비용
| 키 | 빈도 | 최적 깊이 | 그리디 깊이 | 균형 깊이 | 최적에서의 비용 |
|---|---|---|---|---|---|
| a | 100 | 1 | 1 | 2 | 100 |
| b | 1 | 3 | 2 | 1 | 3 |
| c | 1 | 2 | 3 | 2 | 2 |
| d | 1 | 3 | 4 | 3 | 3 |
| 합계 (Σ 빈도 × 깊이) | 108 | ||||
계산 방법
- 1키와 탐색 빈도를 한 줄에 하나씩 «키 빈도» 꼴로 적습니다.
- 2최적 트리의 기대 비용과, 빈도 순 그리디·균형 트리의 비용을 견줍니다.
- 3아래 트리 그림에서 자주 찾는 키가 어느 깊이에 놓였는지 봅니다.
- 4키마다의 깊이 표에서 Σ 빈도 × 깊이가 기대 비용과 맞는지 확인합니다.
자주 묻는 질문
같은 키들로 만들 수 있는 이진 탐색 트리 가운데 기대 탐색 비용 Σ(빈도 × 깊이)가 가장 작은 것입니다. 깊이는 뿌리를 1로 셉니다. 자주 찾는 키를 얕은 곳에 두면 비용이 줄지만, 정렬 순서를 지켜야 해서 마음대로 올릴 수는 없습니다.
그렇지 않습니다. 이진 탐색 트리는 정렬 순서를 지켜야 하므로 어떤 키를 뿌리로 삼으면 그보다 작은 키는 전부 왼쪽, 큰 키는 전부 오른쪽으로 강제됩니다. 빈도가 가장 높은 키가 한쪽 끝에 있으면 그것을 올리는 순간 나머지가 한쪽으로 쏠려 전체가 깊어집니다. 이 계산기의 기본 예(a가 100, 나머지가 1)가 바로 그 경우입니다.
구간 DP입니다. cost[i][j] = min_r (cost[i][r−1] + cost[r+1][j]) + W(i, j)로, W(i,j)는 구간 i..j의 빈도 합입니다. r을 뿌리로 세우면 양쪽 부분트리의 모든 키가 깊이 1씩 깊어지므로 그 구간의 빈도 합이 한 번 더 붙습니다. 이 W 항을 빠뜨리는 것이 가장 흔한 구현 실수이며, 키가 두세 개일 때는 맞다가 네 개부터 어긋납니다.
최적 뿌리가 구간이 커질 때 왼쪽으로 되돌아가지 않는다는 성질(root[i][j−1] ≤ root[i][j] ≤ root[i+1][j])을 이용해 뿌리 후보의 범위를 좁히는 방법입니다. 그냥 짜면 (i, j, r) 세 겹이라 O(n³)인데 이 단조성을 쓰면 O(n²)가 됩니다. 답은 같고 살펴보는 조합의 수만 줄어듭니다.
빈도가 고르다면 충분합니다. 실제로 모든 빈도가 같으면 최적 트리의 비용은 균형 트리와 같습니다. 하지만 빈도가 치우치면 다릅니다. 예를 들어 키가 넷이고 마지막 키만 90번 찾는다면, 가운데를 뿌리로 삼는 균형 트리는 그 키를 깊이 3에 두어 손해를 봅니다.
세지 않습니다. 교과서의 완전한 형태는 키 사이사이의 «없는 값» 구간(더미 키)에도 빈도를 주어 함께 최소화합니다. 이 계산기는 넣은 키를 찾는 경우만 다루므로, 없는 키를 자주 찾는 상황이라면 최적 트리의 모양이 달라질 수 있습니다.
둘 다 구간 DP입니다. «구간을 어디서 자를지»를 모두 시도하고 그 결과를 표에 쌓아 올리는 뼈대가 같으며, 다른 것은 자른 값을 합치는 비용 식뿐입니다. 최적 BST는 여기에 크누스 최적화가 통해 O(n²)까지 줄어드는 점이 다릅니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.
알아두면 좋은 점
- 키는 24개까지 받습니다. 구간 DP는 O(n²)이라 훨씬 커도 되지만 화면에 트리를 그리기 어렵습니다.
- 실패 탐색(없는 키를 찾는 경우)의 빈도는 다루지 않습니다. 넣은 키를 찾는 경우만 셉니다.
- 깊이는 뿌리를 1로 셉니다. 0으로 세는 책도 있어 값이 키 개수만큼 달라 보일 수 있습니다.
- 넣은 순서와 상관없이 키를 정렬해서 다룹니다. 이진 탐색 트리는 정렬 순서를 지켜야 하기 때문입니다.
- 숫자만 넣으면 문자열 사전순이 아니라 크기순으로 정렬합니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.