로그보다 빠른 탐색의 세계 - van Emde Boas Tree 완전 정복

"정렬된 값 중에서 x보다 큰 값을 빠르게 찾으려면?" 대부분의 개발자는 이진 탐색 트리를 떠올립니다.

하지만 빅테크 시스템에서는 log n도 느릴 수 있습니다. 이럴 때 등장하는 고성능 구조가 바로 van Emde Boas

Tree입니다.

O(log log U) 시간 복잡도를 자랑하는 van Emde Boas Tree는 시스템에서 빠른 순위 조회와 최소값 탐색을 가능하게 하는 데이터 구조다.

van Emde Boas Tree란?

van Emde Boas Tree (vEB Tree) 는 정수 키를 갖는 집합에 대해 다음 연산을 모두 O(log log U) 시간에 지원하는 고급 자료구조입니다. 여기서 U는 universe 크기, 즉 가능…