판 엠데 보아스 트리

**판 엠데 보아스 트리**(van Emde Boas tree, ), **vEB 트리** 또는 **판 엠데 보아스 우선순위 큐**라고도 알려진 이 자료 구조는 -비트 정수 키를 사용하는 연관 배열을 구현하는 트리 자료 구조이다. 이 자료 구조는 네덜란드 컴퓨터 과학자 피터 판 엠데 보아스가 이끄는 팀에 의해 1975년에 발명되었다. 모든 연산은  시간(m 비트 연산이 상수 시간에 수행될 수 있다고 가정) 또는 동등하게 O(\log \log M) 시간 안에 수행되며, 여기서 M = 2^m은 트리에 저장될 수 있는 가장 큰 원소이다. 매개변수 M은 트리에 저장된 실제 원소의 수와 혼동되어서는 안 된다. 다른 트리 자료 구조의 성능은 종종 이 매개변수로 측정되기 때문이다.

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

## 지원되는 연산
vEB는 일반적인 연관 배열 연산과 FindNext 및 FindPrevious라는 두 가지 추가 순서 연산을 포함하는 정렬된 연관 배열의 연산을 지원한다:
* Insert: -비트 키를 가진 키/값 쌍 삽입
* Delete: 주어진 키를 가진 키/값 쌍 제거
* Lookup: 주어진 키와 관련된 값 찾기
* FindNext: 주어진 보다 큰 가장 작은 키를 가진 키/값 쌍 찾기
* FindPrevious: 주어진 보다 작은 가장 큰 키를 가진 키/값 쌍 찾기

vEB 트리는 또한 Minimum 및 Maximum 연산을 지원하며, 이는 각각 트리에 저장된 최소 및 최대 원소를 반환한다. 최소 및 최대 원소는 각 트리에 속성으로 저장되므로 이 둘 모두 O(1) 시간에 실행된다.

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

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

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

 **function** FindNext(T, x)
     **if** x \sqrt{M})
     lo = x mod \sqrt{M}

     **if** lo \sqrt{M} i) + FindNext(T.children[i], lo)
     j = FindNext(T.aux, i)
     **return** (\sqrt{M} j) + T.children[j].min
 **end**

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

### 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.max **then**
         T.max = x
     i = floor(x / \sqrt{M})
     lo = x mod \sqrt{M}
     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 * \sqrt{M}
         j = T.aux.min
         T.min = x = hi + T.children[j].min
     i = floor(x / \sqrt{M})
     lo = x mod \sqrt{M}
     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 * \sqrt{M}
             j = T.aux.max
             T.max = hi + T.children[j].max
 **end**

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

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

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

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

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

## 유사한 구조
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일.
* 

분류:탐색 트리