홍라이프 계산기트리 높이 계산기 쉽게 이해하기 — 개념과 원리
탐색 트리의 높이는 한 번 찾을 때 거쳐야 하는 노드 수를 정하므로 검색, 삽입, 삭제 속도를 결정합니다. 이 계산기는 키 n개를 담을 때 이진 트리가 가질 수 있는 최소 높이와, AVL 트리·레드-블랙 트리·B-트리가 보장하는 최악의 높이를 비교합니다. 여기서 높이는 뿌리에서 잎까지 가장 긴 경로에 있는 노드의 층수입니다.
계산 방법
- 포화 이진 트리(최소): ⌈log₂(n + 1)⌉. 높이 h이면 키를 최대 2ʰ − 1개 담기 때문입니다.
- AVL 트리(최대): 약 1.44 · log₂(n + 2) − 0.328
- 레드-블랙 트리(최대): 2 · log₂(n + 1)
- B-트리(최대 층수): ⌊log_t((n + 1) ÷ 2)⌋ + 1. t = ⌈차수 ÷ 2⌉는 뿌리가 아닌 내부 노드의 최소 자식 수입니다.
원리
균형 트리는 한쪽으로 치우치는 정도를 제한해 높이를 O(log n)으로 보장합니다. AVL 트리는 모든 노드에서 두 서브트리의 높이 차가 1 이하입니다. 이런 트리 중 가장 성긴 것이 피보나치 트리이고, 피보나치 수는 황금비 φ ≈ 1.618의 거듭제곱처럼 커지므로 높이는 log_φ n ≈ 1.44 log₂ n을 넘지 않습니다. 레드-블랙 트리는 모든 경로의 검은 노드 수가 같고 빨간 노드가 연속하지 않으므로, 가장 긴 경로가 가장 짧은 경로의 두 배를 넘지 않습니다. B-트리는 노드마다 키를 많이 담고 자식이 최소 t개라 매우 납작합니다. 층 하나가 보통 디스크 페이지 한 번 읽기에 해당하므로 데이터베이스와 파일 시스템이 B-트리를 씁니다.
예제 풀이
- 입력값: 키 n = 1,000,000개, B-트리 차수 256입니다.
- 포화 이진 트리: log₂ 1,000,001 ≈ 19.93을 올려 20층입니다.
- AVL: 1.44 × 19.9316 − 0.328 ≈ 28.37346289입니다.
- 레드-블랙: 2 × 19.9316 ≈ 39.86314002입니다.
- B-트리: t = 128, log₁₂₈(500,000.5) ≈ 2.70이므로 ⌊2.70⌋ + 1 = 3층입니다.
| 키 수 n | 포화 이진 트리 최소 높이 |
|---|---|
| 250,000 | 18 |
| 500,000 | 19 |
| 750,000 | 20 |
| 1e+06 | 20 |
| 1.25e+06 | 21 |
| 1.5e+06 | 21 |
| 2e+06 | 21 |
결과 해석
키가 백만 개여도 균형 이진 트리는 최악의 경우 40번 미만으로 비교하지만, 정렬된 순서로 넣은 일반 이진 탐색 트리는 1,000,000층짜리 목록이 될 수 있습니다. AVL은 조금 더 낮아 검색에 유리하고, 레드-블랙은 갱신할 때 회전이 적습니다. 차수 256인 B-트리는 백만 개 키 중 어느 것이든 노드 3개만 읽으면 찾습니다.
흔한 실수
- 높이 정의를 섞는 경우입니다. 간선 수로 세는 교재에서는 노드 하나의 높이가 0입니다.
- B-트리의 차수(최대 자식 수)와 최소 차수 t를 혼동합니다.
- 실제 높이가 항상 최악값이라고 생각합니다.
자주 묻는 질문
왜 항상 완벽한 균형을 유지하지 않나요?
삽입할 때마다 완벽하게 맞추려면 재구성 비용이 크기 때문에, 조금 더 높은 대신 O(log n)에 갱신하는 방식을 택합니다.
AVL과 레드-블랙 중 무엇이 빠른가요?
읽기가 많으면 AVL이 유리한 경우가 많고, 갱신이 잦으면 레드-블랙이 유리해 표준 라이브러리에서 널리 쓰입니다.
무작위로 넣은 이진 탐색 트리는 얼마나 높나요?
평균 노드 깊이는 약 1.39 log₂ n이지만 최악의 경우는 여전히 n입니다.
출처: G. M. Adelson-Velsky, E. M. Landis, "An algorithm for the organization of information", 1962 · T. H. Cormen 외, Introduction to Algorithms, MIT Press · R. Bayer, E. McCreight, "Organization and maintenance of large ordered indexes", Acta Informatica 1, 1972