반 엠데 보아스 트리(van Emde Boas tree) 계산기
전체 범위 U가 정해진 정수 집합에서 반 엠데 보아스 트리가 successor·predecessor를 O(log log U)에 찾는 과정을 클러스터·요약 구조로 보여줍니다.
0 이상 16 미만 정수. 현재 7개
x=5는 집합에 있는가
있음
min=2 · max=15
사용 방법
- 1전체 범위 U(16·64·256 중 하나)를 고릅니다.
- 2집합에 넣을 원소들을 쉼표로 구분해 넣습니다.
- 3질의할 값을 넣어 소속 여부·successor·predecessor·클러스터 번호를 확인합니다.
자주 묻는 질문
정수 전체 범위(universe) U가 미리 정해져 있을 때, 삽입·탐색·successor(다음 원소)·predecessor(이전 원소)를 모두 O(log log U)에 처리합니다. 일반적인 균형 이진트리의 O(log n)보다 훨씬 빠릅니다.
크기 U인 구조를 √U 크기의 클러스터 √U개로 재귀적으로 쪼개기 때문입니다. 모든 연산이 항상 √U 크기로만 재귀하므로 T(U) = T(√U) + O(1)이 되고, 이를 풀면 O(log log U)가 나옵니다.
어느 클러스터가 비어있지 않은지만 추적하는 √U 크기의 보조 구조입니다. 현재 클러스터 안에서 답을 못 찾으면 요약 구조에서 다음으로 원소가 있는 클러스터를 찾고, 그 클러스터의 최솟값(또는 최댓값)을 답으로 씁니다.
클러스터와 요약 구조가 모두 정확히 √U 크기로 딱 떨어지려면 U가 완전제곱수의 거듭제곱(4, 16, 64, 256, …)이어야 합니다. 이 계산기는 그 경우만 다루는 CLRS 교과서의 기본 형태입니다.
IP 라우팅 테이블, 우선순위 큐, 메모리 관리처럼 다루는 정수 범위가 미리 정해져 있고 매우 빠른 successor/predecessor 조회가 필요한 곳에 쓰입니다. 다만 메모리를 U에 비례해 미리 잡아 둬야 해서 U가 매우 크면 비현실적입니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 이 계산기는 U가 4^k(4, 16, 64, 256, …) 형태인 기본 vEB 트리만 다룹니다. 임의의 U를 지원하는 일반화된 구성은 다루지 않습니다.
- 정확성은 "정렬된 배열을 그냥 훑는" 독립적인 브루트포스 구현과 무작위로 대조해 검증했습니다.
- 메모리 사용량이 U에 비례해서, 원소가 몇 개 안 되더라도 U가 크면 메모리를 많이 씁니다(이 트레이드오프는 이 계산기가 다루지 않습니다).
- CLRS 교과서에 실린 결정적 알고리즘이라 법령·통계 의존이 없어 dataExpiry 등록 대상이 아닙니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 5일 · 결과는 참고용 추정치입니다.