Drzewo van Emde Boasa
Drzewo van Emde Boasa (zwana także drzewo vEB, vEB) – rodzaj kolejki priorytetowej wynalezionej przez holenderski zespół pod przewodnictwem Petera van Emde Boasa. Pozwalają wykonywać operacje typu search, insert, delete, predecessor, successor, minimum, maximum w niezależnym od rozmiaru drzewa czasie o ile (dla dowolnej całkowitej liczby ), które oznacza rozmiar uniwersum wartości, które można przechowywać w strukturze. Struktura odpowiada nałożeniu drzewa stopnia na wektor bitowy. Zapotrzebowanie na pamięć to Puste drzewo można skonstruować w czasie [1].
Literatura naukowa
Koncepcja po raz pierwszy pojawiła się we wstępnej formie w pracy Petera van Emde Boasa z 1975 roku (Preserving order in a forest in less than logarythmic time w Proceedings of the 16th Annual Symposium on Foundations of Computer Sciene), a w późniejszych pracach temat był rozwijany przez niego samego (Preserving order in a forest in less than logarythmic time and linear space w Information Processing letters) w 1977 oraz razem z R. Kaasem i E. Zijstrem (Design and implementation of an efficient priority queue w Mathematical Systems Theory) w 1976[1].
Roman Dementiev, Lutz Kettner, Jens Mehnert i Peter Sanders zaprojektowali nierekurencyjne trójpoziomowe drzewo wyszukiwań, które w ich własnych eksperymentach działało szybciej, niż drzewo van Emde Boasa[2].
Elementy
Niech drzewo van Emde Boasa będzie oznaczone jako vEB(u).
Wyznaczanie elementów
Niech obecność elementu w zbiorze oznacza wartość 1, nieobecność wartość 0. Traktując x jako liczbę całkowitą binarną -bitową, można wykazać, że wartość jest numerem bloku wektora bitowego, w którym się ona znajduje, a także określa najbardziej znaczących bitów wartości x. Wartość jest równa najmniej znaczących bitów x, co jest numerem wartości x w bloku. Oba fakty są tożsame ze stwierdzeniem, że pozycja x w wektorze bitowym (i tym samym jego wartość), to: [1].
Powyższe fakty są stosowane do budowy funkcji pomocniczych w implementacjach drzew van Emde Boasa[1]:
Budowa elementów
Jeśli rozmiar uniwersum nie jest równe rozmiarowi bazowemu 2, to drzewo vEB(u)zawiera[1]:
- Wskaźnik summary do drzewa vEB
- Tablicę cluster[0 ... -1] wskaźników do drzew vEB
- Atrybut min, który przechowuje najmniejszy element w drzewie. Element tu przechowywany nie występuje w żadnym z poddrzew przechowywanych w tablicy cluster.
- Atrybut max, który przechowuje największy element w drzewie.
Jeśli rozmiar uniwersum jest równy 2 (przypadek bazowy), drzewo zawiera jedynie:
- Atrybut min
- Atrybut max
Zmniejszenie złożoności obliczeniowej operacji dzięki wykorzystaniu atrybutów min i max
Istnienie atrybutów min i max pozwala skrócić czas wykonywania poniższych operacji do stałego[1]:
- Operacje MINIMUM i MAXIMUM polegają tylko na podaniu wartości, odpowiednio, atrybutu min lub max. Czas wykonywania zawsze jest stały.
- W operacji SUCCESSOR i PREDECESSOR można uniknąć wywoływania rekurencyjnego w celu sprawdzenia, czy następnik lub poprzednik znajduje się w obrębie bloku high(x), dzięki sprawdzeniu, czy następnik lub poprzednik jest odpowiednio mniejszy, niż atrybut max lub większy, niż atrybut min.
- Jeśli drzewo zawiera tylko jeden element lub jest puste, odpowiednio jeden z atrybutów lub oba zawierają wartość pustą. Pozwala to także skrócić czas działania procedur takich jak INSERT, DELETE, PREDECESSOR, SUCCESSOR do stałego.
Operacje na drzewie
Znajdowanie minimum i maksimum
Ponieważ obie minimum i maksimum są zawarte w atrybutach, obie operacje trwają czas stały:
minimum(v) { return v.min } maximum (v) { return v.max }
Sprawdzanie, czy element należy do zbioru
member(v, x) { if x == v.min || x == v.max return true elseif v.u == 2 return false else return member (v.cluster[high(x)],low(x)) }
Znajdowanie poprzednika i następnika
successor(V,x) { if(V.u == 2) { if (x == 0 && v.max == 1) return 1 else return null } else if v.min != null && x < v.min return v.min else max-low = maximum(v.cluster[high(x)] { if max-low != null && low(x) < max-low { offset = successor (v.cluster[high(x)], low(x)) return index(high(x), offset) } else succ-cluster = successor(v.summary, high(x)) { if succ-cluster == null return null else offset(v.cluster[succ-cluster]) return index(succ-cluster, offset) } } }
Wiersze 2-4 odnoszą się do przypadku bazowego (u = 2). W wierszach 7-10 sprawdzane jest, czy następnik znajduje się w tym samym bloku. Pozostałe instrukcje poszukują następnika w następnych blokach.
predecessor(V,x) { if (V.u == 2) { if (x == 1 && v.min == 0) return 0; else return null; else if (v.max != null && x > v.max) return v.max; else (min-low = minimum(v.cluster[high(x)])) { if min-low != null && low(x) > min-low { offset = predecessor (v.summary, high(x)) { if pred-cluster == null { if (v.min != null && x > v.min) return v.min; else return null; } else offset = maximum(v.cluster[pred-cluster]); return index (pred-cluster, offset); } } } } }
Wstawianie elementu
Pomocnicza procedura, która wstawia elementy do pustego drzewa lub pustego węzła:
empty-tree-insert(V,x) { v.min = x; v.max = x; }
Pseudokod procedury rozbudowanej o wstawianie elementu do niepustego drzewa:
insert(V, x) { if (V.min == NULL) { empty-tree-insert(V, x); return; } if (x < V.min) { swap(x , V.min) } if (V.u > 2) { if (minimum(V.cluster[high(x)]) == NULL) { insert(V.summary,high(x); empty-tree-insert(V.cluster[high(x)],low(x)); } else { insert(V.cluster[high(x)],low(x)); } } if (x > V.max) { V.max = x; } return; }
Usuwanie elementu
delete (V,x) { if (V.min == V.max) { V.min = NULL; V.max = NULL; } else if (V.u == 2) { if (x == 0) { V.min = 1; } else { V.max = 0; V.max = V.min; } } else if (X == V.min) { first-cluster = minimum(V.summary); x = index(first-cluster,minimum(V.cluster[first-cluster])); V.min = x; } delete(V.cluster[high(x)], low(x)); if (minimum(V.cluster[high(x)]) == NULL) { delete(V.summary,high(x)); if (x == V.max) { summary-max = maximum(V.summary); if (summary-max == NULL) { V.max = V.min; else { V.max = index(summary-max,maximum(V.cluster[summary-max])); } } } else if {x == V.max) { V.max = index(high(x),maximum(V.cluster[high(x)])); } } } }
Drzewo van Emde Boasa zredukowanego rozmiaru
Można zmodyfikować drzewo van Emde Boasa w taki sposób, by wymagania pamięciowe zmniejszyć wielkości uniwersum do wielkości przechowywanych wartości[1]:
- Atrybut V.cluster nie jest przechowywany jako zwykła tablica wskaźników do drzew, lecz jako tablica z haszowaniem przechowywana jako tablica dynamiczna, do których są przypisane kolejne drzewa zredukowanego rozmiaru (analogicznie do „zwykłych drzew”, gdzie przechowywane są wskaźniki do „zwykłych” drzew w zwyczajnej tablicy). Aby znaleźć i-ty blok, szukamy klucza i w czasie stałym, za pomocą jednego wyszukiwania.
- Przechowywane są tylko niepuste bloki. Próba wyszukania pustego bloku zwraca wartość pustą.
- Atrybut V.summary ma wartość pustą, jeśli wszystkie bloki są puste. W przeciwnym wypadku, V.summary jest wskaźnikiem na drzewo o rozmiarze uniwersum
Przypisy
- ↑ a b c d e f g Thomas H.T.H. Cormen Thomas H.T.H. i inni, Wprowadzenie do algorytmów, KrzysztofK. Diks (tłum.) i inni, wyd. VII (I w PWN), Warszawa: PWN, 2015, ISBN 978-83-01-16911-4 (pol.).
- ↑ Roman Dementiev, Lutz Kettner, Jens Mehnert, Peter Sanders: Engineering a sorted list data structure for 32 bit keys. Proceedings of Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, styczeń 2004.