Van Emde Boas Tree

Van Emde Boas Tree

우선순위 큐 연산(삽입, 삭제, 최소/최대값 찾기, 전임자/후임자 찾기)을 O(log log n) 시간에 수행하는 트리 자료구조로, 재귀적 분할 정복과 요약 정보를 활용하여 이진 탐색 트리보다 빠른 연산 제공

목적: 초고속 우선순위 큐, 정수 집합 연산, 범위 쿼리 최적화

특징: O(log log n) 연산, 재귀적 구조, 요약(summary) 사용, 우주 크기(u) 의존

구성요소: 우주 크기(u), cluster(하위 트리 배열), summary(cluster 요약), min/max(최소/최대값)

동작 원리: u 크기 우주를 √u 개의 cluster로 분할 → 각 cluster는 √u 크기 → 재귀적으로 동일 구조 → summary는 cluster 존재 여부 추적

연산: insert/delete/min/max/predecessor/successor 모두 O(log log u)

시간 복잡도: O(log log u), u = 우주 크기(가능한 키 범위)

공간 복잡도: O(u) - 희소 집합에서 비효율, O(n log u) 최적화 버전 존재

장점: 매우 빠른 연산(O(log log n)), 결정적 성능, 정수 키 최적화

단점: 높은 공간 복잡도(O(u)), 우주 크기 제한, 구현 복잡도, 정수만 지원

적용사례: 고속 라우팅 테이블, IP 룩업, 범위 쿼리, 정수 집합 연산

비교: vEB Tree(O(log log n)/공간 많음) vs BST(O(log n)/공간 적음) vs 해시(O(1)/순서 없음)

연관: 우선순위 큐, 정수 집합, 범위 쿼리, Fusion Tree