Drzewo Van Emde Boas

Drzewo van Emde Boasa
Drzewo van Emde Boasa
Typ	Drzewo niebinarne
Wynaleziony	1975
Wynalezione przez	Petera van Emde Boasa
Złożoność czasowa w notacji dużego O
Algorytm
Algorytm	Przeciętny
Przestrzeń	O ( M )
Szukaj	O (log log M )
Wstawić	O (log log M )
Usuwać	O (log log M )

Drzewo van Emde Boasa ( wymowa niderlandzka: [vɑn ˈɛmdə ˈboːɑs] ), znane również jako drzewo vEB lub kolejka priorytetowa van Emde Boasa , to drzewiasta struktura danych , która implementuje tablicę asocjacyjną z $m$ -bitowymi kluczami całkowitymi. Został wynaleziony przez zespół kierowany przez holenderskiego informatyka Petera van Emde Boasa w 1975 roku. Wykonuje wszystkie operacje w czasie $O (log m) (zakładając, że$ $m$ operacja bitowa może być wykonywana w czasie stałym) lub równoważnie w czasie $O (log log M) , gdzie$ $M = 2 m$ to największy element, jaki można zapisać w drzewie. Parametru $M$ nie należy mylić z rzeczywistą liczbą elementów przechowywanych w drzewie, za pomocą której często mierzy się wydajność innych drzewiastych struktur danych.

Drzewo vEB ma słabą efektywność przestrzenną. Na przykład do przechowywania 32-bitowych liczb całkowitych (tj. gdy $m =32$ ) wymaga to $M =2 32$ bity pamięci. Istnieją jednak podobne struktury danych o równie dobrej wydajności czasowej i przestrzeni $O (n)$ , gdzie $n$ jest liczbą przechowywanych elementów.

Obsługiwane operacje

vEB obsługuje operacje na uporządkowanej tablicy asocjacyjnej , która obejmuje zwykłe operacje na tablicach asocjacyjnych wraz z dwiema dodatkowymi operacjami porządkowania , FindNext i FindPrevious :

Wstaw : wstaw parę klucz/wartość z $m$ -bitowym kluczem
Usuń : usuń parę klucz/wartość z danym kluczem
Wyszukiwanie : znajdź wartość powiązaną z danym kluczem
FindNext : znajdź parę klucz/wartość z najmniejszym kluczem, który jest większy niż podane $k$
FindPrevious : znajdź parę klucz/wartość z największym kluczem, który jest mniejszy niż podane $k$

Drzewo vEB obsługuje również operacje Minimum i Maximum , które zwracają odpowiednio minimalny i maksymalny element przechowywany w drzewie. Oba działają w $O (1)$ , ponieważ minimalny i maksymalny element są przechowywane jako atrybuty w każdym drzewie.

Funkcjonować

Przykładowe drzewo van Emde Boasa o wymiarze 5 i wstawioną strukturą aux korzenia po 1, 2, 3, 5, 8 i 10.

Dla uproszczenia niech $log 2 m = k$ dla pewnej liczby całkowitej k . Zdefiniuj $M = 2 m$ . Drzewo vEB T we wszechświecie ${0, ..., M -1$ } ma węzeł główny, w którym przechowywana jest tablica T.children o długości √ M . T.children[i] jest wskaźnikiem do drzewa vEB, które odpowiada za wartości ${i \sqrt M, ..., (i +1) \sqrt M -1$ }. Dodatkowo T przechowuje dwie wartości T.min i T.max oraz pomocnicze drzewo vEB T.aux .

Dane są przechowywane w drzewie vEB w następujący sposób: Najmniejsza wartość aktualnie w drzewie jest przechowywana w T.min , a największa w T.max . Zauważ, że T.min nie jest przechowywany nigdzie indziej w drzewie vEB, podczas gdy T.max jest. Jeśli T jest puste, to używamy konwencji, że T.max=−1 i T.min=M . Każda inna wartość x jest przechowywana w poddrzewie T.children[i] , gdzie $i = ⌊ x / \sqrt M ⌋$ . Drzewo pomocnicze T.aux śledzi, które dzieci są niepuste, więc T.aux zawiera wartość j wtedy i tylko wtedy, gdy T.children[j] jest niepuste.

Znajdź następny

Operacja FindNext(T, x) , która szuka następnika elementu x w drzewie vEB, przebiega następująco: Jeśli x <T.min , to wyszukiwanie jest zakończone, a odpowiedzią jest T.min . Jeśli x≥T.max to następny element nie istnieje, zwróć M. W przeciwnym razie niech $i = ⌊ x / \sqrt M ⌋$ . Jeśli x<T.children[i].max to szukana wartość jest zawarta w T.children[i] , więc wyszukiwanie przebiega rekurencyjnie w T.dzieci[i] . W przeciwnym razie szukamy następcy wartości i w T.aux . To daje nam indeks j pierwszego poddrzewa, które zawiera element większy niż x . Następnie algorytm zwraca T.children[j].min . Element znaleziony na poziomie potomnym musi zostać złożony z wysokich bitów, aby utworzyć kompletny następny element.

         
        
    
    
         funkcja  ZnajdźNastępny(T, x)  jeśli  x < T.min  to  zwróć  T.min  jeśli  x ≥ T.max  to  // brak następnego elementu  zwróć  M i = floor(x/  √  M  ) lo = x mod  √  M  jeśli  lo < T.dzieci[i].max  następnie  powrót  (  √  M  i) + ZnajdźNastępny(T.dzieci[i], lo) j = ZnajdźNastępny(T.aux, i)  powrót  (  √  M  j) + T.dzieci[j] .min  koniec

Należy zauważyć, że w każdym przypadku algorytm wykonuje pracę $O (1)$ $m, a następnie prawdopodobnie 2$ $M .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 1/2 / wykonuje$ rekursję na poddrzewie we wszechświecie o rozmiarze ( wszechświat -bitowy). $_$ czasu _ $_(log m) = O (log log M)$ .

Wstawić

Wywołanie insert(T, x) , które wstawia wartość x do drzewa vEB T , działa w następujący sposób:

Jeśli T jest puste, ustawiamy T.min = T.max = x i gotowe.
W przeciwnym razie, jeśli x<T.min to wstawiamy T.min do poddrzewa i odpowiedzialnego za T.min , a następnie ustawiamy T.min = x . Jeśli T.children[i] było wcześniej puste, wstawimy również i do T.aux
W przeciwnym razie, jeśli x>T.max to wstawiamy x do poddrzewa i odpowiadającego za x i następnie ustawiamy T.max = x . Jeśli T.children[i] było wcześniej puste, wstawimy również i do T.aux
W przeciwnym razie T.min< x < T.max , więc wstawiamy x do poddrzewa i odpowiedzialnego za x . Jeśli T.children[i] było wcześniej puste, wstawimy również i do T.aux .

W kodzie:

 
     funkcja  Wstaw(T, x)  jeśli  T.min > T.max  to  // T jest puste  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  Wstaw(T.dzieci[i] , lo)  if  T.children[i].min == T.children[i].max  then  Insert(T.aux, i)  end

Kluczem do efektywności tej procedury jest to, że wstawienie elementu do pustego drzewa vEB zajmuje $O (1)$ czasu. Tak więc, chociaż algorytm czasami wykonuje dwa wywołania rekurencyjne, dzieje się tak tylko wtedy, gdy pierwsze wywołanie rekurencyjne dotyczyło pustego poddrzewa. $_$ powtarzalność _

Usuwać

Usuwanie z drzew vEB jest najtrudniejszą z operacji. Wywołanie Delete(T, x) , które usuwa wartość x z drzewa vEB T, działa w następujący sposób:

Jeśli T.min = T.max = x , to x jest jedynym elementem przechowywanym w drzewie i ustawiamy T.min = M i T.max = −1 , aby wskazać, że drzewo jest puste.
W przeciwnym razie, jeśli x == T.min , to musimy znaleźć drugą najmniejszą wartość y w drzewie vEB, usunąć ją z jej bieżącej lokalizacji i ustawić T.min=y . Drugą najmniejszą wartością y jest T.children[T.aux.min].min , więc można ją znaleźć w czasie $O (1)$ . Usuwamy y z poddrzewa, które je zawiera.
Jeśli x≠T.min i x≠T.max to usuwamy x z poddrzewa T.children[i] , które zawiera x .
Jeśli x == T.max , to będziemy musieli znaleźć drugą co do wielkości wartość y w drzewie vEB i ustawić T.max=y . Zaczynamy od usunięcia x tak jak w poprzednim przypadku. Wtedy wartość y to T.min lub T.children[T.aux.max].max , więc można ją znaleźć w czasie $O (1) .$
W każdym z powyższych przypadków, jeśli usuniemy ostatni element x lub y z dowolnego poddrzewa T.children[i] , to usuniemy również i z T.aux .

W kodzie:

     funkcja  Usuń(T, x)  jeśli  T.min == T.max == x  wtedy  T.min = M T.max = −1  powrót  jeśli  x == T.min  to  hi = T.aux.min *  √  M  j = T.aux.min T.min = x = hi + T.dzieci[j].min i = podłoga(x /  √  M  ) lo = x mod  √  M  Usuń(T.dzieci[i], lo)  if  T.dzieci[i] jest puste  , to  Usuń(T.aux, i)  jeśli  x == T.maks.  to 
         jeśli  T.aux jest puste  , to  T.max = T.min  inaczej  hi = T.aux.max *  √  M  j = T.aux.max T.max = hi + T.dzieci[j].max  koniec

Ponownie, skuteczność tej procedury zależy od tego, że usunięcie z drzewa vEB, które zawiera tylko jeden element, zajmuje tylko stały czas. W szczególności drugie wywołanie Delete jest wykonywane tylko wtedy, gdy przed usunięciem x był jedynym elementem w T.children[i] .

Dyskusja

Założenie, że $log m$ jest liczbą całkowitą, jest niepotrzebne. Operacje ${\ Displaystyle x {\ sqrt {M}}}$ i ${\ Displaystyle x {\ bmod {\ sqrt {M}}}}$ można zastąpić, biorąc tylko wyższego rzędu $⌈ m / 2 ⌉$ i odpowiednio $⌊ m /2⌋$ bitów $x$ . Na dowolnej istniejącej maszynie jest to bardziej wydajne niż dzielenie lub obliczenia reszty.

W praktycznych implementacjach, zwłaszcza na maszynach z instrukcjami przesuwania o k i znajdowania pierwszego zera , wydajność można dodatkowo poprawić, przełączając się na tablicę bitów po osiągnięciu $m$ równego rozmiarowi słowa (lub jego małej wielokrotności). Ponieważ wszystkie operacje na pojedynczym słowie są stałe w czasie, nie wpływa to na wydajność asymptotyczną, ale pozwala uniknąć większości przechowywania wskaźników i kilku dereferencji wskaźników, osiągając dzięki tej sztuczce znaczne praktyczne oszczędności czasu i miejsca.

Oczywistą optymalizacją drzew vEB jest odrzucanie pustych poddrzew. To sprawia, że drzewa vEB są dość zwarte, gdy zawierają wiele elementów, ponieważ żadne poddrzewa nie są tworzone, dopóki nie trzeba do nich czegoś dodać. Początkowo każdy dodany element tworzy około $log(m)$ nowych drzew zawierających łącznie około $m /2 wskaźników.$ W miarę wzrostu drzewa coraz więcej poddrzew jest ponownie wykorzystywanych, zwłaszcza te większe. W pełnym drzewie $M$ elementów tylko $O(M)$ wykorzystywana jest przestrzeń. Co więcej, w przeciwieństwie do binarnego drzewa wyszukiwania, większość tej przestrzeni jest wykorzystywana do przechowywania danych: nawet dla miliardów elementów wskaźniki w pełnym drzewie vEB liczą się w tysiącach.

Opisana powyżej implementacja wykorzystuje wskaźniki i zajmuje całkowitą przestrzeń $O (M) = O (2 m)$ , proporcjonalną do rozmiaru kluczowego wszechświata. To może być rozumiane w następujący sposób. Nawrót to ${\ Displaystyle S (M) = O ({\ sqrt {M}}) + ({\ sqrt {M}} +1)\cdot S({\sqrt {M}})}$ . Rozwiązanie, które doprowadziłoby do ${\ Displaystyle S (M) \ w (1 + {\ sqrt {M}}) ^ {\ log \log M}+\log \log M\cdot O({\sqrt {M}})}$ . Na szczęście można również pokazać, że $S (M) = M -2$ przez indukcję.

Podobne struktury

O $(M) przez drzewa vEB jest ogromnym obciążeniem, chyba że przechowywana jest$ duża część wszechświata kluczy. Jest to jeden z powodów, dla których drzewa vEB nie są popularne w praktyce. To ograniczenie można rozwiązać, zmieniając tablicę używaną do przechowywania elementów podrzędnych na inną strukturę danych. Jedną z możliwości jest użycie tylko ustalonej liczby bitów na poziom, co skutkuje trie . Alternatywnie, każdą tablicę można zastąpić tablicą mieszającą , redukując przestrzeń do $O (n)$ (gdzie $n$ to liczba elementów przechowywanych w strukturze danych) kosztem losowości struktury danych. Inne struktury danych, w tym x-szybkie próby i y-szybkie próby, mają porównywalne czasy aktualizacji i zapytań do drzew vEB, a także wykorzystują losowe tablice skrótów, aby zmniejszyć przestrzeń odpowiednio do $O (n log M)$ i $O (n) .$

Implementacje

Istnieje zweryfikowana implementacja w Isabelle (asystent weryfikacji) . Udowodniono zarówno poprawność funkcjonalną, jak i ograniczenia czasowe. Można wygenerować wydajny imperatywny standardowy kod ML .

Zobacz też

Dalsza lektura

Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Instytut Technologii w Massachusetts. 6.851: Zaawansowane struktury danych (wiosna 2012). Wykład 11 notatki . 22 marca 2012 r.
van Emde Boas, P .; Kaas, R.; Zijlstra, E. (1976). „Projekt i realizacja wydajnej kolejki priorytetowej”. Teoria systemów matematycznych . 10 : 99–127. doi : 10.1007/BF01683268 .

Drzewa struktur danych
Drzewa wyszukiwania ( zestawy dynamiczne / tablice asocjacyjne )	2–3 2–3–4 AA (a, b) AVL B B+ B* B ^x ( Optymalne ) Wyszukiwanie binarne Taniec HTree Interwał Statystyka zamówień ( Lewicowy ) Czerwono-czarny Kozioł ofiarny Pochylenie T skarb UB Zrównoważony wagowo
stosy	Dwójkowy Dwumianowy Brodal Fibonacciego Lewicowy Łączenie w pary Krzywy van Emde Boasa Słaby
Próby	Ctrie C-trie (skompresowany ADT) Haszysz Źródło Przyrostek Wyszukiwanie trójskładnikowe X-szybki Y-szybko
Drzewa partycjonowania danych przestrzennych	Piłka BK BSP kartezjański Hilberta R k -d ( domniemana k -d ) M Metryczny MVP Octree PH Priorytet R Kwadrat R R+ R* Człon wiceprezes X
Inne drzewa	Okładka Wykładniczy Fenwick Palec Indeks drzewa fraktalnego Połączenie Kalendarz mieszania iOdległość K-ary Prawe rodzeństwo lewego dziecka Połącz / wytnij Scalanie o strukturze dziennika Merkle PQ Zakres SPQR Szczyt