판 엠데 보아스 트리

판 엠데 보아스 트리(van Emde Boas tree, ), vEB 트리 또는 판 엠데 보아스 우선순위 큐라고도 알려진 이 자료 구조는 -비트 정수 키를 사용하는 연관 배열을 구현하는 트리 자료 구조이다. 이 자료 구조는 네덜란드 컴퓨터 과학자 피터 판 엠데 보아스가 이끄는 팀에 의해 1975년에 발명되었다.Peter van Emde Boas: Preserving order in a forest in less than logarithmic time (Proceedings of the 16th Annual Symposium on Foundations of Computer Science 10: 75-84, 1975) 모든 연산은  시간(m 비트 연산이 상수 시간에 수행될 수 있다고 가정) 또는 동등하게  시간 안에 수행되며, 여기서 은 트리에 저장될 수 있는 가장 큰 원소이다. 매개변수 은 트리에 저장된 실제 원소의 수와 혼동되어서는 안 된다. 다른 트리 자료 구조의 성능은 종종 이 매개변수로 측정되기 때문이다.

표준 vEB 트리는 의 비효율적인 공간 효율성을 가진다. 예를 들어, 32비트 정수를 저장할 때(즉, 일 때)  비트의 저장 공간이 필요하다. 이를 해결하기 위해 vEB 트리를 수정하여  공간을 달성하거나, 동등한 점근 시간 효율성과  공간 효율성(여기서 은 저장된 원소의 수)을 가진 유사한 자료 구조를 사용할 수 있다.

지원되는 연산
vEB는 일반적인 연관 배열 연산과 FindNext 및 FindPrevious라는 두 가지 추가 순서 연산을 포함하는 정렬된 연관 배열의 연산을 지원한다:Gudmund Skovbjerg Frandsen: Dynamic algorithms: Course notes on van Emde Boas trees (PDF)  (오르후스 대학교, 컴퓨터 과학과)
 Insert: -비트 키를 가진 키/값 쌍 삽입
 Delete: 주어진 키를 가진 키/값 쌍 제거
 Lookup: 주어진 키와 관련된 값 찾기
 FindNext: 주어진 보다 큰 가장 작은 키를 가진 키/값 쌍 찾기
 FindPrevious: 주어진 보다 작은 가장 큰 키를 가진 키/값 쌍 찾기

vEB 트리는 또한 Minimum 및 Maximum 연산을 지원하며, 이는 각각 트리에 저장된 최소 및 최대 원소를 반환한다.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT 프레스, 2009. . Chapter 20: The van Emde Boas tree, pp. 531–560. 최소 및 최대 원소는 각 트리에 속성으로 저장되므로 이 둘 모두  시간에 실행된다.

기능
섬네일|alt=판 엠데 보아스 트리 예시 |차원 5의 판 엠데 보아스 트리와 1, 2, 3, 5, 8, 10이 삽입된 후 루트의 보조 구조의 예시. 어떤 정수 에 대해 라고 하자. 으로 정의하자. 유니버스 에 걸친 vEB 트리 는 길이 의 배열 을 저장하는 루트 노드를 가진다. 는 값 을 담당하는 vEB 트리 포인터이다. 또한 T는 두 값  및 와 보조 vEB 트리 를 저장한다.

데이터는 vEB 트리에 다음과 같이 저장된다: 현재 트리에 있는 가장 작은 값은 에 저장되고 가장 큰 값은 에 저장된다. 은 vEB 트리의 다른 곳에 저장되지 않는 반면 는 저장된다는 점에 유의한다. T가 비어 있다면  및 으로 간주한다. 다른 값 는 인 서브트리 에 저장된다. 보조 트리 는 어떤 자식이 비어 있지 않은지 추적하므로, 가 비어 있지 않은 경우에만 는 값 를 포함한다.

FindNext
vEB 트리에서 원소 x의 후속자를 검색하는 연산 는 다음과 같이 진행된다: 만약 이면 검색이 완료되고, 답은 이다. 만약 이면 다음 원소가 존재하지 않으므로 M을 반환한다. 그렇지 않으면 라고 하자. 만약 이면, 검색 중인 값은 에 포함되어 있으므로 검색은 에서 재귀적으로 진행된다. 그렇지 않으면, 에서 값 i의 후속자를 검색한다. 이것은 x보다 큰 원소를 포함하는 첫 번째 서브트리의 인덱스 j를 제공한다. 그런 다음 알고리즘은 을 반환한다. 자식 레벨에서 발견된 원소는 전체 다음 원소를 형성하기 위해 상위 비트와 결합되어야 한다.

 function FindNext(T, x)
     if x < T.min then
         return T.min
     if x ≥ T.max then // 다음 원소 없음
         return M
     i = floor(x/)
     lo = x mod 

     if lo < T.children[i].max then
         return ( i) + FindNext(T.children[i], lo)
     j = FindNext(T.aux, i)
     return ( j) + T.children[j].min
 end

어떤 경우에도 알고리즘은  작업을 수행한 다음 크기  (m/2 비트 유니버스)의 유니버스에 걸친 서브트리에서 재귀를 수행할 수 있다는 점에 유의한다. 이는 실행 시간에 대해 의 재귀 관계를 제공하며, 이는 으로 해결된다.

Insert
vEB 트리 에 값 를 삽입하는 호출 는 다음과 같이 작동한다:

 T가 비어 있으면 로 설정하고 완료한다.
 그렇지 않으면, 이면 을 을 담당하는 서브트리 에 삽입한 다음 로 설정한다. 만약 가 이전에 비어 있었다면, 도 에 삽입한다.
 그렇지 않으면, 이면 를 를 담당하는 서브트리 에 삽입한 다음 로 설정한다. 만약 가 이전에 비어 있었다면, 도 에 삽입한다.
 그렇지 않으면, 이므로 를 를 담당하는 서브트리 에 삽입한다. 만약 가 이전에 비어 있었다면, 도 에 삽입한다.

코드:
 function Insert(T, x)
     if T.min == x || T.max == x then // x는 이미 삽입됨
         return
     if T.min > T.max then // T가 비어 있음
         T.min = T.max = x;
         return
     if x < T.min then
         swap(x, T.min)
     if x > T.max then
         T.max = x
     i = floor(x / )
     lo = x mod 
     Insert(T.children[i], lo)
     if T.children[i].min == T.children[i].max then
         Insert(T.aux, i)
 end

이 절차의 효율성에 대한 핵심은 빈 vEB 트리에 원소를 삽입하는 데  시간이 걸린다는 것이다. 따라서 알고리즘이 때로는 두 번의 재귀 호출을 하더라도, 이는 첫 번째 재귀 호출이 빈 서브트리에 있었을 때만 발생한다. 이는 이전과 동일한 실행 시간 재귀 관계인 을 제공한다.

Delete
vEB 트리에서 삭제는 가장 까다로운 연산 중 하나이다. vEB 트리 T에서 값 x를 삭제하는 호출 는 다음과 같이 작동한다:

 만약 이면 x는 트리에 저장된 유일한 원소이며 트리가 비어 있음을 나타내기 위해  및 로 설정한다.
 그렇지 않으면, 만약 이면 vEB 트리에서 두 번째로 작은 값 y를 찾아 현재 위치에서 삭제한 다음 로 설정해야 한다. 두 번째로 작은 값 y는 이므로  시간에 찾을 수 있다. y를 포함하는 서브트리에서 y를 삭제한다.
 만약  및 이면 x를 포함하는 서브트리 에서 x를 삭제한다.
 만약 이면 vEB 트리에서 두 번째로 큰 값 y를 찾아 로 설정해야 한다. 이전 경우와 같이 x를 삭제하는 것부터 시작한다. 그러면 값 y는 이거나 이므로  시간에 찾을 수 있다.
 위 경우 중 어느 하나라도, 어떤 서브트리 에서 마지막 원소 x 또는 y를 삭제하면 에서도 i를 삭제한다.

코드:
 function Delete(T, x)
     if T.min == T.max == x then
         T.min = M
         T.max = −1
         return
     if x == T.min then
         hi = T.aux.min * 
         j = T.aux.min
         T.min = x = hi + T.children[j].min
     i = floor(x / )
     lo = x mod 
     Delete(T.children[i], lo)
     if T.children[i] is empty then
         Delete(T.aux, i)
     if x == T.max then
         if T.aux is empty then
             T.max = T.min
         else
             hi = T.aux.max * 
             j = T.aux.max
             T.max = hi + T.children[j].max
 end

다시 한번, 이 절차의 효율성은 단 하나의 원소만 포함하는 vEB 트리에서 삭제하는 데 상수 시간만 걸린다는 사실에 달려 있다. 특히, 두 번째 Delete 호출은 삭제 이전에 x가 에 유일한 원소였을 때만 실행된다.

실제 적용
이 정수라는 가정은 불필요하다.  및  연산은 각각 의 상위  비트와 하위  비트를 취함으로써 대체될 수 있다. 기존의 어떤 기계에서든 이것은 나눗셈 또는 나머지 계산보다 더 효율적이다.

실제 구현에서, 특히 k 시프트 및 첫 번째 0 찾기 명령을 가진 기계에서는 이 워드 크기(또는 그 작은 배수)와 같아질 때 비트 배열로 전환함으로써 성능을 더욱 향상시킬 수 있다. 단일 워드에 대한 모든 연산은 상수 시간이므로 이는 점근적 성능에 영향을 미치지 않지만, 대부분의 포인터 저장 및 여러 포인터 역참조를 피하여 이 트릭으로 시간 및 공간에서 상당한 실질적인 절약을 달성한다.

vEB 트리의 최적화는 빈 서브트리를 폐기하는 것이다. 이는 vEB 트리가 많은 원소를 포함할 때 매우 컴팩트하게 만든다. 왜냐하면 어떤 것이 추가될 필요가 있을 때까지 서브트리가 생성되지 않기 때문이다. 초기에는 추가되는 각 원소가 약 개의 새로운 트리를 생성하며, 이들은 모두 합쳐서 약 개의 포인터를 포함한다. 트리가 성장함에 따라 더 많은 서브트리가 재사용되며, 특히 큰 서브트리가 그렇다. 

위에서 설명한 구현은 포인터를 사용하며, 키 유니버스의 크기에 비례하는 총  공간을 차지한다. 이는 다음과 같이 볼 수 있다. 재귀 관계는 이다.
귀납법으로 임을 보일 수 있다.

유사한 구조
vEB 트리의  공간 사용량은 키 유니버스의 큰 부분이 저장되지 않는 한 엄청난 오버헤드이다. 이것이 vEB 트리가 실제로 인기가 없는 이유 중 하나이다. 이 제한은 자식을 저장하는 데 사용되는 배열을 다른 자료 구조로 변경함으로써 해결될 수 있다. 한 가지 가능성은 각 레벨당 고정된 수의 비트만 사용하는 것으로, 이는 트라이 (컴퓨팅)로 이어진다. 또는 각 배열을 해시 테이블로 대체하여 공간을 로 줄일 수 있다(여기서 은 자료 구조에 저장된 원소의 수) 이 경우 자료 구조는 무작위화된다.

x-고속 트라이와 더 복잡한 y-고속 트라이는 vEB 트리와 유사한 업데이트 및 쿼리 시간을 가지며, 무작위 해시 테이블을 사용하여 사용되는 공간을 줄인다. x-고속 트라이는  공간을 사용하는 반면, y-고속 트라이는  공간을 사용한다.

융합 트리는 유한 유니버스에서 w-비트 정수에 대한 연관 배열을 구현하는 또 다른 유형의 트리 자료 구조이다. 이들은 워드 수준 병렬 처리 및 비트 조작 기술을 사용하여 선행자/후속자 쿼리 및 업데이트에 대해  시간을 달성한다. 여기서 는 워드 크기이다. 융합 트리는  공간을 사용하며 해싱 또는 지수 트리를 사용하여 동적으로 만들 수 있다.

구현
이사벨 (증명 보조기)에 검증된 구현이 있다. 기능적 정확성과 시간 경계 모두 증명되었다.
효율적인 명령형 표준 ML 코드를 생성할 수 있다.

 같이 보기 
 정수 정렬
 탱고 트리

 각주 

추가 자료

 Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Massachusetts Institute of Technology. 6.851: Advanced Data Structures (Spring 2012). 강의 노트 11. 2012년 3월 22일.


분류:탐색 트리