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 $\mathrm {O} (log_{2}log_{2}u),$ o ile $u=2^{k$ (dla dowolnej całkowitej liczby $k$ ), które oznacza rozmiar uniwersum wartości, które można przechowywać w strukturze. Struktura odpowiada nałożeniu drzewa stopnia ${\sqrt {u$ na wektor bitowy. Zapotrzebowanie na pamięć to $\mathrm {O} (u).$ Puste drzewo można skonstruować w czasie $\Theta (u)$ ^[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ą $\lg _{2}{u$ -bitową, można wykazać, że wartość $\lfloor {\tfrac {x}{\lfloor {\sqrt {u}\rfloor }\rfloor$ jest numerem bloku wektora bitowego, w którym się ona znajduje, a także określa ${\tfrac {\log _{2}{u}{2$ najbardziej znaczących bitów wartości x. Wartość $x{\bmod {\lfloor }{\sqrt {u}\rfloor$ jest równa ${\tfrac {log_{2}{u}{2$ 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: $x=\lfloor {\tfrac {x}{\sqrt {u}\rfloor +{\tfrac {log_{2}{u}{2$ ^[1].

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

$high(x)=\lfloor {\tfrac {x}{\lfloor {\sqrt {u}\rfloor }\rfloor ,$
$low(x)=x{\bmod {\lfloor }{\sqrt {u}\rfloor ,$
$index(x)=high(x)+low(x).$

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 $(\lceil {\sqrt {u}\rceil ).$
Tablicę cluster[0 ... $\lceil {\sqrt {u}\rceil$ -1] wskaźników do $\lceil {\sqrt {u}\rceil$ drzew vEB $(\lfloor {\sqrt {u}\rfloor ).$
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 ${\sqrt {u}.$

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.

[:0-1] ↑ ^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.).

[2] 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.

[1]

[2]