반 엠드 보아스 트리

이 글의 어조나 문체는 위키백과에서 사용되는 백과사전적 어조를 반영하지 못할 수도 있다. 제안사항은 위키피디아의 더 나은 기사 작성 안내서를 참조하십시오.(2021년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

판엠데보아스나무
유형	비이진 트리
발명된	1975
발명된 사람	피터 판 엠드 보아스
큰 O 표기법에서의 시간 복잡성
알고리즘. 평균 최악의 경우 공간 O(M) O(M) 검색 O(로그 로그 M) O(로그 로그 M) 삽입하다 O(로그 로그 M) O(로그 로그 M) 삭제 O(로그 로그 M) O(로그 로그 M)

vEB 트리 또는 van Emde Boas 우선 순위 대기열이라고도 하는 판 엠드 보아스 트리(Dutch 발음: [vɑn ˈɛmdə ˈboːs])는 m비트 정수 키와 연관 배열을 구현하는 트리 데이터 구조다.O(log m) 시간에 모든 작업을 수행하거나 O(log log M) 시간에 동등하게 수행한다. 여기서 M = 2는^m 트리에 저장할 수 있는 요소의 최대 수입니다.M은 다른 트리 데이터 구조의 성능을 종종 측정하는 트리에 저장된 요소의 실제 수와 혼동해서는 안 된다.vEB 트리는 많은 요소를 포함할 때 공간 효율이 좋다.1975년 네덜란드 컴퓨터 과학자 피터 반 엠드 보아스가 이끄는 팀에 의해 발명되었다.^[1]

지원되는 작업

vEB는 일반적인 연관 배열 작업과 더불어 FindNext 및 FindPrevious의 두 가지 추가 주문 작업을 포함하는 정렬된 연관 배열의 작업을 지원한다.^[2]

• 삽입: m-비트 키로 키/값 쌍 삽입
• 삭제: 지정된 키를 사용하여 키/값 쌍을 제거
• 조회: 지정된 키와 연결된 값 찾기
• FindNext: 주어진 k보다 큰 가장 작은 키를 가진 키/값 쌍 찾기
• FindPrevious: 주어진 k보다 작은 가장 큰 키를 가진 키/값 쌍을 찾음

또한 vEB 트리는 트리에 저장된 최소 및 최대 요소를 각각 반환하는 최소 및 최대 작업을 지원한다.^[3]최소 요소와 최대 요소가 각 트리에 속성으로 저장되기 때문에 이 두 요소는 모두 O(1) 시간에 실행된다.

함수

단순성을 위해 일부 정수 k에 대해 로그₂ m = k를 두십시오.M = 2^m. vEB 트리 정의{0, ...을 통한 T, M-1}에는 길이가 √M인 어레이 T. children을 저장하는 루트 노드가 있다.T.children[i]은 {i√M, ..., (i+1)√M-1} 값을 담당하는 vEB 트리에 대한 포인터다.또한 T는 보조 vEB 트리 T.aux뿐만 아니라 T.min과 T.max 두 개의 값을 저장한다.

데이터는 다음과 같이 vEB 트리에 저장된다.현재 트리에서 가장 작은 값은 T.min에 저장되며 가장 큰 값은 T.max에 저장된다.T.max는 vEB 트리의 다른 곳에 저장되지 않는 반면 T.min은 다른 곳에 저장되지 않는다는 점에 유의하십시오.만약 T가 비어있다면 우리는 T.max=-1과 T.min=M이라는 관례를 사용한다.다른 값 x는 하위 트리 T.children[i]에 저장된다. 여기서 i = xx/mM⌋.보조 트리 T.aux는 어떤 아이가 비어 있지 않은지 추적하기 때문에 T.aux는 T.children[j]이 비어 있지 않은 경우에만 값 j를 포함한다.

다음 찾기

vEB 트리에서 x 요소의 후속 요소를 검색하는 FindNext(T, x) 작업은 다음과 같이 진행된다.x<T.min이면 검색이 완료되고 정답은 T.min이다.x≥T.max가 없으면 M을 반환한다.그렇지 않으면 i = ⌊x/√M⌋. if x<T.children[i].검색되는 최대값은 T.children[i]에 포함되어 있으므로 검색은 T.children[i]에서 반복적으로 진행된다.그렇지 않으면, 우리는 T.aux에서 가치 i의 후계자를 찾는다.이것은 우리에게 x보다 큰 요소를 포함하는 첫 번째 하위 트리의 지수 j를 제공한다.그러면 알고리즘은 T. children[j.min]을 반환한다.어린이 수준에서 발견되는 요소는 다음 완전한 요소를 형성하기 위해 높은 비트로 구성되어야 한다.

함수 FindNext(T, x) 만약 x < T.min이면 T.min을 반환하고 x ≥ T.max이면 // 다음 원소는 Mi = 바닥(x//M) lo = lo < T.children[i]이면 x mod √M을 반환하지 않는다.max then return (118 mi) + FindNext(T.children[i], lo) j = FindNext(T.aux, i) return (118 m j) + T.children[j]최소 끝

참고, 어떤 경우에도 알고리즘 다음 가능한 하위 트리를 M.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output을 지닌 우주에 recurses O(1)작업을 수행하다. .sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}1/2(한m/2 비트 우주).$이것$은 O(log m) = O(log m) = O(log log M) = O(log log M$)$= O(log log M$)$로 분해되는 T$(m / 2$)의 실행 시간에 대해 재발을 제공한다.

삽입하다

값 x를 vEB 트리 T에 삽입하는 콜 인서트(T, x)는 다음과 같이 작동한다.

1. T가 비어 있으면 T.min = T.max = x를 설정하면 끝이다.
2. 그렇지 않으면, 만약 x<T.min이 내가 T.min을 담당하는 하위 트리에 T.min을 삽입하고 T.min = x를 설정한다. T.children[i]이 이전에 비어 있었다면 i도 T.aux에 삽입한다.
3. 그렇지 않으면, 만약 x>T.max가 x를 담당하는 하위 트리에 x를 삽입하고 T.max = x를 설정한다. T.children[i]이 이전에 비어 있었다면, i도 T.aux에 삽입한다.
4. 그렇지 않으면 T.min< x < T.max 그래서 우리는 x를 담당하는 하위 트리에 x를 삽입한다. 만약 T.children[i]이 이전에 비어 있었다면, i도 T.aux에 삽입한다.

코드:

function Insert(T, x)     if T.min > T.max then // T is empty         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 / √M)     lo = x mod √M     Insert(T.children[i], lo)     if T.children[i].min == T. children[i]최대 다음 삽입(T.aux, i) 끝

이 절차의 효율성의 핵심은 빈 vEB 트리에 요소를 삽입하는 데 O(1) 시간이 걸린다는 것이다.그래서 알고리즘이 때때로 두 번의 재귀전화를 하기도 하지만, 이는 첫 번째 재귀전화가 빈 하위 트리에 들어갔을 때에만 발생한다.$이것$은 T (${\displaystyle m}$)${\displaystyle }$= ${\displaystyle T}$( ${\displaystyle m\mathrm{}}$/ ${\displaystyle 2}$)${\displaystyle }$+ ${\displaystyle \mathrm{O}}$( 1 )${\displaystyle T(m)=T(m/2)+O(1)}$의 동일한 작동 시간 재발을 제공한다.

삭제

VEB 트리에서 삭제하는 것이 수술 중 가장 까다롭다.vEB 트리 T에서 값 x를 삭제하는 호출 삭제(T, x)는 다음과 같이 작동한다.

1. T.min = T.max = x인 경우 x는 트리에 저장된 유일한 요소이며 T.min = M, T.max = -1을 설정하여 트리가 비어 있음을 표시한다.
2. 그렇지 않으면 x == T.min이면 vEB 트리에서 두 번째로 작은 값 y를 찾아서 현재 위치에서 삭제하고 T.min=y를 설정해야 한다.두 번째로 작은 값 y는 T.children[T.aux.min]이므로 O.(1) 시간 내에 찾을 수 있다.우리는 그것을 포함하는 하위 트리에서 y를 삭제한다.
3. x≠T.min과 x≠T.max가 있으면 x가 들어 있는 하위 트리 T.children[i]에서 x를 삭제한다.
4. x == T.max이면 vEB 트리에서 두 번째로 큰 y 값을 찾아서 T.max=y를 설정해야 한다.우리는 이전 사례와 같이 x를 삭제하는 것으로 시작한다.그 다음 y 값은 T.min 또는 T.children[T.aux.max] 중 하나이므로 O.(1) 시간 내에 찾을 수 있다.
5. 위의 경우 중 하나라도 T.children[i] 하위 트리에서 마지막 요소 x 또는 y를 삭제하면 t.aux에서도 i를 삭제한다.

코드:

함수 삭제(T, x) T.min == T.max == x인 경우 T.min = M.max = -1 return x == T.min인 경우 hi = T.aux.min * =m j = t.aux.min = x = hi + children[j]min     i = floor(x / √M)     lo = x mod √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 * √M             j = T.aux.max             T.max = hi + T.children[j].최대 끝

다시 한 번, 이 절차의 효율성은 오직 하나의 요소만을 포함하는 vEB 트리에서 삭제하는 것은 일정한 시간만 소요된다는 사실에 달려 있다.특히 두 번째 Delete call은 삭제 전 T.children[i]에서 x가 유일한 요소인 경우에만 실행된다.

토론

로그 m이 정수라는 가정은 불필요하다.연산$$ $x{\displaystyle }$ ${\displaystyle M\sqrt{}}$ ${\$ x${\sqrt{M}}$과 x ${\displaystyle mod}$ ${\displaystyle M\sqrt{}}$ ${\${\sqrt${M}}}}$은 각각 고차 orderm/2⌉의 x 비트와 저차만 취하여 대체할 수 있다.기존의 어떤 기계에서도, 이것은 분할이나 나머지 계산보다 더 효율적이다.

위에서 설명한 구현은 포인터를 사용하며 O(M) = O(2)의^m 총 공간을 차지한다.이것은 다음과 같이 볼 수 있다.The recurrence is ${\displaystyle S(M)=O({\sqrt {M}})+({\sqrt {M}}+1)\cdot S({\sqrt {M}})}$. Resolving that would lead to ${\displaystyle S(M)\in (1+{\sqrt {M}})^{\log \log M}+\log \log M\cdot O({\sqrt {M}})}$. One can은 다행히도 S(M) = M-2 인덕션에 의해서도 나타난다.^[4]

특히 Shift-by-k가 있는 기계에서 처음 제로 지침을 찾는 실제 구현에서는 단어 크기(또는 그 작은 배수)에 도달하면 비트 배열로 전환하여 성능을 더욱 향상시킬 수 있다.한 단어의 모든 연산이 일정한 시간이기 때문에 이것은 점증적 성능에 영향을 미치지 않지만, 포인터 저장과 여러 포인터 참조의 대부분을 피하여 이 기술로 시간과 공간에서 상당한 실질적인 절약을 달성한다.

vEB 트리의 분명한 최적화는 빈 하위 트리를 폐기하는 것이다.이것은 많은 요소들을 포함하고 있을 때 vEB 트리를 매우 압축하게 만든다. 왜냐하면 어떤 것이 추가될 필요가 있을 때까지 하위 트리가 생성되지 않기 때문이다.처음에 추가된 각 요소는 모두 합쳐 약 m/2 포인터를 포함하는 로그(m) 새 트리에 대해 생성한다.나무가 자라면서 점점 더 많은 하위 트리, 특히 큰 하위 트리들이 재사용된다.2개의^m 원소가 있는 풀 트리에서는 O(2^m) 공간만 사용된다.게다가, 바이너리 검색 트리와는 달리, 이 공간의 대부분은 데이터를 저장하는 데 사용되고 있다. 수십억 개의 요소에도 불구하고, 수천 개의 완전한 vEB 트리 숫자에 있는 포인터들이다.

그러나 작은 나무의 경우 VEB 나무와 관련된 오버헤드가 엄청나다.$$$M{\displaystyle \sqrt{}}$ ${\$ 이것이 그들이 실제로 인기가 없는 한 가지 이유다.이 한계를 해결하는 한 가지 방법은 레벨당 고정된 비트 수만 사용하는 것이며, 이로 인해 트리어가 발생한다.또는 각 테이블을 해시 테이블로 대체하여 데이터 구조를 랜덤화하는 비용을 들여 공간을 O(n log M)(여기서 n은 데이터 구조에 저장된 요소의 수)로 줄일 수 있다.y-fast try와 x-fast try를 포함한 다른 구조는 유사한 업데이트 및 쿼리 시간을 가지며 공간을 O(n) 또는 O(n 로그 M)로 줄이기 위해 랜덤화된 해시 테이블을 사용하는 것이 제안되었다.

구현

이사벨(증거보조)에 검증된 구현이 있다.^[5]기능적 정확성과 시간 한계가 모두 입증되었다.효율적인 필수 표준 ML 코드가 생성될 수 있다.

참고 항목

• 정수 정렬
• 전임자 문제
• 퓨전 트리
• 탱고나무
• X-fast trie
• Y-fast trie

참조

추가 읽기