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].
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].
Niech drzewo van Emde Boasa będzie oznaczone jako vEB(u).
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]:
Jeśli rozmiar uniwersum nie jest równe rozmiarowi bazowemu 2, to drzewo vEB(u)zawiera[1]:
Jeśli rozmiar uniwersum jest równy 2 (przypadek bazowy), drzewo zawiera jedynie:
Istnienie atrybutów min i max pozwala skrócić czas wykonywania poniższych operacji do stałego[1]:
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
}
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))
}
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);
}
}
}
}
}
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;
}
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)]));
}
}
}
}
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]: