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

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

Jeśli rozmiar uniwersum nie jest równe rozmiarowi bazowemu 2, to drzewo vEB(u)zawiera^[1]:

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

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.

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

• 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 ${\displaystyle {\sqrt {u}}.}$