판 엠데 보아스 트리

delete_worst = O(\log \log M) **판 엠데 보아스 트리**(van Emde Boas tree, vɑn ˈɛmdə ˈboːɑs), **vEB 트리** 또는 **판 엠데 보아스 우선순위 큐**라고도 알려진 이 자료 구조는 m-비트 정수 키를 사용하는 연관 배열을 구현하는 트리 자료 구조이다. 이 자료 구조는 네덜란드 컴퓨터 과학자 피터 판 엠데 보아스가 이끄는 팀에 의해 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) 모든 연산은 O(log m) 시간(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라는 두 가지 추가 순서 연산을 포함하는 정렬된 연관 배열의 연산을 지원한다:Gudmund Skovbjerg Frandsen: Dynamic algorithms: Course notes on van Emde Boas trees (PDF) date=2015-09-23 (오르후스 대학교, 컴퓨터 과학과) * Insert: m-비트 키를 가진 키/값 쌍 삽입 * Delete: 주어진 키를 가진 키/값 쌍 제거 * Lookup: 주어진 키와 관련된 값 찾기 * FindNext: 주어진 k보다 큰 가장 작은 키를 가진 키/값 쌍 찾기 * FindPrevious: 주어진 k보다 작은 가장 큰 키를 가진 키/값 쌍 찾기 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. 최소 및 최대 원소는 각 트리에 속성으로 저장되므로 이 둘 모두 O(1) 시간에 실행된다.
# 기능
차원 5의 판 엠데 보아스 트리와 1, 2, 3, 5, 8, 10이 삽입된 후 루트의 보조 구조의 예시. 어떤 정수 k에 대해 \log_2 m = k라고 하자. M = 2^m으로 정의하자. 유니버스 \\{0, \ldots, M - 1\\}에 걸친 vEB 트리 T는 길이 \sqrt{M}의 배열 T.children을 저장하는 루트 노드를 가진다. T.children[i]는 값 \\{i \sqrt{M}, \ldots, (i + 1) \sqrt{M} - 1\\}을 담당하는 vEB 트리 포인터이다. 또한 T는 두 값 T.min 및 T.max와 보조 vEB 트리 T.aux를 저장한다. 데이터는 vEB 트리에 다음과 같이 저장된다: 현재 트리에 있는 가장 작은 값은 T.min에 저장되고 가장 큰 값은 T.max에 저장된다. T.min은 vEB 트리의 다른 곳에 저장되지 않는 반면 T.max는 저장된다는 점에 유의한다. T가 비어 있다면 1=T.max=−1 및 1=T.min=M으로 간주한다. 다른 값 x는 i = \lfloor x / \sqrt{M} \rfloor인 서브트리 T.children[i]에 저장된다. 보조 트리 T.aux는 어떤 자식이 비어 있지 않은지 추적하므로, T.children[j]가 비어 있지 않은 경우에만 T.aux는 값 j를 포함한다.
## FindNext
vEB 트리에서 원소 x의 후속자를 검색하는 연산 FindNext(T, x)는 다음과 같이 진행된다: 만약 모노|xi = \lfloor x / \sqrt{M} \rfloor라고 하자. 만약 x T.max이면 x를 x를 담당하는 서브트리 i에 삽입한 다음 1=T.max = x로 설정한다. 만약 T.children[i]가 이전에 비어 있었다면, i도 T.aux에 삽입한다. # 그렇지 않으면, 모노|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 트리에 원소를 삽입하는 데 O(1) 시간이 걸린다는 것이다. 따라서 알고리즘이 때로는 두 번의 재귀 호출을 하더라도, 이는 첫 번째 재귀 호출이 빈 서브트리에 있었을 때만 발생한다. 이는 이전과 동일한 실행 시간 재귀 관계인 1=T(m)=T(m/2) + O(1)을 제공한다.
## Delete
vEB 트리에서 삭제는 가장 까다로운 연산 중 하나이다. vEB 트리 T에서 값 x를 삭제하는 호출 Delete(T, x)는 다음과 같이 작동한다: # 만약 1=T.min = T.max = x이면 x는 트리에 저장된 유일한 원소이며 트리가 비어 있음을 나타내기 위해 1=T.min = M 및 1=T.max = −1로 설정한다. # 그렇지 않으면, 만약 1=x == T.min이면 vEB 트리에서 두 번째로 작은 값 y를 찾아 현재 위치에서 삭제한 다음 1=T.min=y로 설정해야 한다. 두 번째로 작은 값 y는 T.children[T.aux.min].min이므로 O(1) 시간에 찾을 수 있다. y를 포함하는 서브트리에서 y를 삭제한다. # 만약 x≠T.min 및 x≠T.max이면 x를 포함하는 서브트리 T.children[i]에서 x를 삭제한다. # 만약 1=x == T.max이면 vEB 트리에서 두 번째로 큰 값 y를 찾아 1=T.max=y로 설정해야 한다. 이전 경우와 같이 x를 삭제하는 것부터 시작한다. 그러면 값 y는 T.min이거나 T.children[T.aux.max].max이므로 O(1) 시간에 찾을 수 있다. # 위 경우 중 어느 하나라도, 어떤 서브트리 T.children[i]에서 마지막 원소 x 또는 y를 삭제하면 T.aux에서도 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가 T.children[i]에 유일한 원소였을 때만 실행된다.
## 실제 적용
log m이 정수라는 가정은 불필요하다. x\sqrt{M} 및 x\bmod\sqrt{M} 연산은 각각 x의 상위 ⌈m/2⌉ 비트와 하위 ⌊m/2⌋ 비트를 취함으로써 대체될 수 있다. 기존의 어떤 기계에서든 이것은 나눗셈 또는 나머지 계산보다 더 효율적이다. 실제 구현에서, 특히 k 시프트 및 첫 번째 0 찾기 명령을 가진 기계에서는 m이 워드 크기(또는 그 작은 배수)와 같아질 때 비트 배열로 전환함으로써 성능을 더욱 향상시킬 수 있다. 단일 워드에 대한 모든 연산은 상수 시간이므로 이는 점근적 성능에 영향을 미치지 않지만, 대부분의 포인터 저장 및 여러 포인터 역참조를 피하여 이 트릭으로 시간 및 공간에서 상당한 실질적인 절약을 달성한다. vEB 트리의 최적화는 빈 서브트리를 폐기하는 것이다. 이는 vEB 트리가 많은 원소를 포함할 때 매우 컴팩트하게 만든다. 왜냐하면 어떤 것이 추가될 필요가 있을 때까지 서브트리가 생성되지 않기 때문이다. 초기에는 추가되는 각 원소가 약 log(m)개의 새로운 트리를 생성하며, 이들은 모두 합쳐서 약 m/2개의 포인터를 포함한다. 트리가 성장함에 따라 더 많은 서브트리가 재사용되며, 특히 큰 서브트리가 그렇다. 위에서 설명한 구현은 포인터를 사용하며, 키 유니버스의 크기에 비례하는 총 O(M) = O(2m) 공간을 차지한다. 이는 다음과 같이 볼 수 있다. 재귀 관계는 S(M) = O( \sqrt{M}) + (\sqrt{M}+1) \cdot S(\sqrt{M}) 이다. 귀납법으로 S(M) = O(M)임을 보일 수 있다.access-date=27 May 2011
# 유사한 구조
vEB 트리의 O(M) 공간 사용량은 키 유니버스의 큰 부분이 저장되지 않는 한 엄청난 오버헤드이다. 이것이 vEB 트리가 실제로 인기가 없는 이유 중 하나이다. 이 제한은 자식을 저장하는 데 사용되는 배열을 다른 자료 구조로 변경함으로써 해결될 수 있다. 한 가지 가능성은 각 레벨당 고정된 수의 비트만 사용하는 것으로, 이는 트라이 (컴퓨팅)로 이어진다. 또는 각 배열을 해시 테이블로 대체하여 공간을 O(n log log M)로 줄일 수 있다(여기서 n은 자료 구조에 저장된 원소의 수) 이 경우 자료 구조는 무작위화된다. x-고속 트라이와 더 복잡한 y-고속 트라이는 vEB 트리와 유사한 업데이트 및 쿼리 시간을 가지며, 무작위 해시 테이블을 사용하여 사용되는 공간을 줄인다. x-고속 트라이는 O(n log M) 공간을 사용하는 반면, y-고속 트라이는 O(n) 공간을 사용한다. 융합 트리는 유한 유니버스에서 w-비트 정수에 대한 연관 배열을 구현하는 또 다른 유형의 트리 자료 구조이다. 이들은 워드 수준 병렬 처리 및 비트 조작 기술을 사용하여 선행자/후속자 쿼리 및 업데이트에 대해 O(logw n) 시간을 달성한다. 여기서 w는 워드 크기이다.language=en 융합 트리는 O(n) 공간을 사용하며 해싱 또는 지수 트리를 사용하여 동적으로 만들 수 있다.
# 구현
이사벨 (증명 보조기)에 검증된 구현이 있다.access-date=26 November 2021 기능적 정확성과 시간 경계 모두 증명되었다. 효율적인 명령형 표준 ML 코드를 생성할 수 있다.
## 추가 자료
참고 자료 시작 * Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Massachusetts Institute of Technology. 6.851: Advanced Data Structures (Spring 2012). 강의 노트 11. 2012년 3월 22일. * doi=10.1007/BF01683268 참고 자료 끝 전거 통제 위키데이터 속성 추적 분류:탐색 트리