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 .

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.

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.

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: .

Powyższe fakty są stosowane do budowy funkcji pomocniczych w implementacjach drzew van Emde Boasa:

Budowa elementów Jeśli rozmiar uniwersum nie jest równe rozmiarowi bazowemu 2, to drzewo vEB(u)zawiera: 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: 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: 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

Kategoria:Struktury danych