Van Emde Boas Baum – Wikipedia
EIN van Emde Boas Baum ((Niederländische Aussprache: [vɑn ‘ɛmdə ‘boːɑs]), auch bekannt als vEB-Baum oder Prioritätswarteschlange von van Emde Boasist eine Baumdatenstruktur, die ein assoziatives Array mit implementiert m-bit Integer-Schlüssel. Es führt alle Operationen in aus Ö(Log m) Zeit oder gleichwertig in Ö(Protokoll Protokoll M.) Zeit, wo M. = 2m ist die maximale Anzahl von Elementen, die im Baum gespeichert werden können. Das M. ist nicht zu verwechseln mit der tatsächlichen Anzahl der im Baum gespeicherten Elemente, an denen häufig die Leistung anderer Baumdatenstrukturen gemessen wird. Der vEB-Baum weist eine gute Raumeffizienz auf, wenn er viele Elemente enthält, wie unten erläutert. Es wurde 1975 von einem Team unter der Leitung des niederländischen Informatikers Peter van Emde Boas erfunden.[1]
Unterstützte Operationen[edit]
Ein vEB unterstützt die Operationen eines geordnetes assoziatives ArrayDies beinhaltet die üblichen assoziativen Array-Operationen zusammen mit zwei weiteren bestellen Operationen, Nächstes finden und FindPrevious::[2]
- Einfügen: Fügen Sie ein Schlüssel / Wert-Paar mit einem ein m-bit Schlüssel
- Löschen: Entfernen Sie das Schlüssel / Wert-Paar mit einem bestimmten Schlüssel
- Nachschlagen: Finden Sie den Wert, der einem bestimmten Schlüssel zugeordnet ist
- Nächstes finden: Finden Sie das Schlüssel / Wert-Paar mit dem kleinsten Schlüssel, der größer als ein gegebener ist k
- FindPrevious: Finden Sie das Schlüssel / Wert-Paar mit dem größten Schlüssel, der kleiner als ein gegebener ist k
Ein vEB-Baum unterstützt auch die Operationen Minimum und Maximal, die das im Baum gespeicherte minimale und maximale Element zurückgeben.[3] Diese laufen beide ein Ö(1) Zeit, da das minimale und maximale Element als Attribute in jedem Baum gespeichert sind.
Wie es funktioniert[edit]
Der Einfachheit halber sei Log2m = k für eine ganze Zahl k. Definieren M. = 2m. Ein vEB-Baum T. über das Universum {0, …, M.−1} hat einen Stammknoten, der ein Array speichert T. Kinder von Länge √M.. T. Kinder[i] ist ein Zeiger auf einen vEB-Baum, der für die Werte verantwortlich ist {ich√M., …, (ich+1)√M.−1}. Zusätzlich, T. speichert zwei Werte T.min und T.max sowie einen zusätzlichen vEB-Baum T.aux.
Daten werden wie folgt in einem vEB-Baum gespeichert: Der kleinste aktuell im Baum enthaltene Wert wird in gespeichert T.min und der größte Wert wird in gespeichert T.max. Beachten Sie, dass T.min wird währenddessen nirgendwo anders im vEB-Baum gespeichert T.max ist. Wenn T. Ist leer, dann verwenden wir die Konvention, dass T.max = -1 und T. min = M.. Jeder andere Wert x wird im Teilbaum gespeichert T. Kinder[i] wo ich = ⌊x/.√M.⌋. Der Hilfsbaum T.aux Verfolgt, welche Kinder nicht leer sind T.aux enthält den Wert j dann und nur dann, wenn T. Kinder[j] ist nicht leer.
Nächstes finden[edit]
Die Operation FindNext (T, x) das sucht nach dem Nachfolger eines Elements x In einem vEB-Baum wird wie folgt vorgegangen: If x Dann ist die Suche abgeschlossen und die Antwort lautet T.min. Wenn x≥T.max dann existiert das nächste Element nicht, gib M zurück. Andernfalls lass ich = x/.√M.. Wenn x[i].max dann ist der gesuchte Wert in enthalten T. Kinder[i] Die Suche wird also rekursiv in fortgesetzt T. Kinder[i]. Ansonsten suchen wir nach dem Wert ich im T.aux. Dies gibt uns den Index j des ersten Teilbaums, der ein Element enthält, das größer als ist x. Der Algorithmus kehrt dann zurück T. Kinder[j].Mindest. Das auf der untergeordneten Ebene gefundene Element muss mit den hohen Bits zusammengesetzt werden, um ein vollständiges nächstes Element zu bilden.
function FindNext(T, x)
if x < T.min then
return T.min
if x ≥ T.max then // no next element
return M
i = floor(x/√M)
lo = x mod √M
if lo < T.children[i].max then
return (√M i) + FindNext(T.children[i], lo)
j = FindNext(T.aux, i)
return (√M j) + T.children[j].min
end
Beachten Sie, dass der Algorithmus in jedem Fall ausgeführt wird Ö(1) arbeiten und dann möglicherweise auf einem Teilbaum über ein Universum von Größe rekursiv M.1/.2 (ein m/.2 Bit Universum). Dies ergibt eine Wiederholung für die Laufzeit von
T.((m)=T.((m/.2)+Ö((1){ Anzeigestil T (m) = T (m / 2) + O (1)}, die sich auflöst Ö(Log m) = Ö(Protokoll Protokoll M.).
Einfügen[edit]
Der Anruf einfügen (T, x) das fügt einen Wert ein x in einen vEB-Baum T. funktioniert wie folgt:
- Wenn T. ist leer dann setzen wir T.min = T.max = x und wir sind fertig.
- Ansonsten wenn x dann fügen wir ein T.min in den Teilbaum ich verantwortlich für T.min und dann einstellen T.min = x. Wenn T. Kinder[i] war vorher leer, dann fügen wir auch ein ich in T.aux
- Ansonsten wenn x> T.max dann fügen wir ein x in den Teilbaum ich verantwortlich für x und dann einstellen T. max = x. Wenn T. Kinder[i] war vorher leer, dann fügen wir auch ein ich in T.aux
- Andernfalls, T. min also fügen wir ein x in den Teilbaum ich verantwortlich für x. Wenn T. Kinder[i] war vorher leer, dann fügen wir auch ein ich in T.aux.
In Code:
function Insert(T, x)
if T.min > T.max then // T is empty
T.min = T.max = x;
return
if x < T.min then
swap(x, T.min)
if x > T.max then
T.max = x
i = floor(x / √M)
lo = x mod √M
Insert(T.children[i], lo)
if T.children[i].min == T.children[i].max then
Insert(T.aux, i)
end
Der Schlüssel zur Effizienz dieses Verfahrens besteht darin, dass das Einfügen eines Elements in einen leeren vEB-Baum erforderlich ist Ö(1) Zeit. Obwohl der Algorithmus manchmal zwei rekursive Aufrufe ausführt, tritt dies nur auf, wenn sich der erste rekursive Aufruf in einem leeren Teilbaum befand. Dies ergibt die gleiche Laufzeitwiederholung von
T.((m)=T.((m/.2)+Ö((1){ Anzeigestil T (m) = T (m / 2) + O (1)}wie vorher.
Löschen[edit]
Das Löschen aus vEB-Bäumen ist die schwierigste Operation. Der Anruf Löschen (T, x) das löscht einen Wert x von einem vEB-Baum T arbeitet wie folgt:
- Wenn T.min = T.max = x dann x ist das einzige Element, das im Baum gespeichert ist und das wir festlegen T. min = M. und T.max = -1 um anzuzeigen, dass der Baum leer ist.
- Ansonsten wenn x == T.min dann müssen wir den zweitkleinsten Wert finden y Löschen Sie es im vEB-Baum von seinem aktuellen Speicherort und legen Sie es fest T.min = y. Der zweitkleinste Wert y ist T. Kinder[T.aux.min].Mindest, so kann es in gefunden werden Ö(1) Zeit. Wir löschen y aus dem Teilbaum, der es enthält.
- Wenn x ≠ T.min und x ≠ T.max dann löschen wir x aus dem Teilbaum T. Kinder[i] das beinhaltet x.
- Wenn x == T.max dann müssen wir den zweitgrößten Wert finden y im vEB-Baum und setzen T. max = y. Wir beginnen mit dem Löschen von x wie im vorherigen Fall. Dann Wert y entweder T.min oder T. Kinder[T.aux.max].max, so kann es in gefunden werden Ö(1) Zeit.
- In jedem der oben genannten Fälle, wenn wir das letzte Element löschen x oder y von jedem Teilbaum T. Kinder[i] dann löschen wir auch ich von T.aux
In Code:
function Delete(T, x)
if T.min == T.max == x then
T.min = M
T.max = −1
return
if x == T.min then
hi = T.aux.min * √M
j = T.aux.min
T.min = x = hi + T.children[j].min
i = floor(x / √M)
lo = x mod √M
Delete(T.children[i], lo)
if T.children[i] is empty then
Delete(T.aux, i)
if x == T.max then
if T.aux is empty then
T.max = T.min
else
hi = T.aux.max * √M
j = T.aux.max
T.max = hi + T.children[j].max
end
Die Effizienz dieses Verfahrens hängt wiederum von der Tatsache ab, dass das Löschen aus einem vEB-Baum, der nur ein Element enthält, nur konstante Zeit benötigt. Insbesondere wird die letzte Codezeile nur ausgeführt, wenn x war das einzige Element in T. Kinder[i] vor dem Löschen.
Python-Implementierung[edit]
from math import ceil, log2
"""
van Emde Boas Tree is a data structure which gives O(log(log(u))
query time for operations like
insert, search, delete, successor and predecessor
VEB class contains attribute
min, max, u, w, cluster and summary
initially min=max=NULL
u = size of universe (the range of total possible entries)
w = word length (number of bits in u)
w = log2(u)
cluster is an array of VEB structures of size of sqrt(u)
summary is a VEB of size sqrt(u)
when the size of VEB structure reaches we don't store clusters and summary vector
min and max are enough to store this structure.
"""
class VEB:
"""Index of x can be determined as the
cluster number and the position inside the cluster
for example lets consider 11
in binary it is written as 1011
so first half parts of the binary strinig give cluster number
and 2nd half gives the postiton inside cluster
cluster number= int(10)= 2
position inside cluster= int(11)=3
so 11 is in 2nd cluster at 3rd position
where counting starts from 0th position
0,1,2,3|4,5,6,7|8,9,10,11|12,13,14,15
^
here we use 'c' to denote cluster number
and 'i' to denote index inside the cluster
so x can be represented as
where x = c * sqrt(u) + i
"""
def high(self, x):
# high(x)=x//int(sqrt(u))
return x >> (self.w // 2)
def low(self, x):
# low(x)= x%int(sqrt(u))
return x & (1 << (self.w // 2)) - 1
def index(self, i, j):
# return i*int(sqrt(self.u))+j
return i << (self.w // 2) | j
def __init__(self, u):
"""
This have been implemented using hash table
to reduce the space complexity from O(U) to O(n*log(log(u))
because u can be very large. for example if word size = 64 bits
u= 2^64 = 16 million TB which can't be stored practically on ram.
where as n*log*log*u can be O(3n) which can be easily stored.
I have a different code for array implementation too.
"""
self.w = ceil(log2(u))
# self.u = 2 ** self.w
self.min = self.max = None
if self.w >= 1: # when u==2^w=2 min and max are enough so we stop recursion
self.cluster = {}
self.summary = None
def member(self, x):
"""Function to check if x is present in tree or not."""
if x == self.min or x == self.max:
return True
elif self.w == 1:
return False
else:
c = self.high(x)
i = self.low(x)
if c in self.cluster:
return self.cluster[c].member(i)
else:
return False
def insert(self, x):
if self.min is None:
self.min = x
self.max = x
return
else:
if x < self.min:
x, self.min = self.min, x
c = self.high(x)
i = self.low(x)
if self.w > 1:
if c not in self.cluster:
self.cluster[c] = VEB(2 ** (self.w // 2))
if self.cluster[c].min is None:
if self.summary is None:
self.summary = VEB(2 ** (self.w // 2))
self.summary.insert(c)
if c not in self.cluster:
self.cluster[c] = VEB(2 ** (self.w // 2))
self.cluster[c].insert(i)
if x > self.max:
self.max = x
def succesor(self, x):
if self.w == 1:
if x == 0 and self.max == 1:
return 1
else:
return None
elif self.min is not None and x < self.min:
return self.min
else:
c = self.high(x)
i = self.low(x)
if c in self.cluster:
maxlow = self.cluster[c].max
else:
maxlow = None
if maxlow is not None and i < maxlow:
offset = self.cluster[c].succesor(i)
return self.index(c, offset)
else:
if self.summary is not None:
succ_cluster = self.summary.succesor(self.high(x))
else:
succ_cluster = None
if succ_cluster is None:
return None
else:
offset = self.cluster[succ_cluster].min
return self.index(succ_cluster, offset)
def predecessor(self, x):
if self.w == 1:
if x == 1 and self.min == 0:
return 0
else:
return None
elif self.max is not None and x > self.max:
return self.max
else:
c = self.high(x)
i = self.low(x)
if c in self.cluster:
min_low = self.cluster[c].min
else:
min_low = None
if min_low is not None and i > min_low:
offset = self.cluster[c].predecessor(i)
return self.index(c, offset)
else:
if self.summary is not None:
prev_cluster = self.summary.predecessor(c)
else:
prev_cluster = None
if prev_cluster is None:
if self.min is not None and x > self.min:
return self.min
else:
return None
else:
offset = self.cluster[prev_cluster].max
return self.index(prev_cluster, offset)
def delete(self, x):
if self.min is None:
return
if x < self.min or x > self.max:
return
if self.min == self.max:
self.min = self.max = None
elif self.w == 1:
if x == 0:
self.min = 1
else:
self.min = 0
self.max = self.min
else:
c = self.high(x)
i = self.low(x)
if x == self.min:
if self.summary:
first_cluster = self.summary.min
else:
first_cluster = None
if first_cluster:
x = self.index(first_cluster, self.cluster[first_cluster].min)
self.min = x
if c in self.cluster:
self.cluster[c].delete(i)
if self.cluster[c].min is None:
self.summary.delete(c)
if x == self.max:
summary_max = self.summary.max
if summary_max is None:
self.max = self.min
else:
self.max = self.index(summary_max, self.cluster[summary_max].max)
elif x == self.max:
self.max = self.index(c, self.cluster[c].max)
Diskussion[edit]
Die Annahme, dass Log m ist eine ganze Zahl ist nicht notwendig. Die Operationen
xM.{ displaystyle x { sqrt {M}}}und
xmodM.{ displaystyle x { bmod { sqrt {M}}}}
kann ersetzt werden, indem nur eine höhere Ordnung genommen wird ⌈m/ 2⌉ und die niedrigere Ordnung ⌊m/ 2⌋ Stücke von x, beziehungsweise. Auf jeder vorhandenen Maschine ist dies effizienter als Teilungs- oder Restberechnungen.
Die oben beschriebene Implementierung verwendet Zeiger und belegt einen Gesamtraum von Ö((M.) = Ö(2m). Dies kann wie folgt gesehen werden. Die Wiederholung ist
S.((M.)=Ö((M.)+((M.+1)⋅S.((M.){ displaystyle S (M) = O ({ sqrt {M}}) + ({ sqrt {M}} + 1) cdot S ({ sqrt {M}})}. Das zu lösen würde dazu führen
S.((M.)∈((1+M.)LogLogM.+LogLogM.⋅Ö((M.){ displaystyle S (M) in (1 + { sqrt {M}}) ^ { log log M} + log log M cdot O ({ sqrt {M}})}
. Das kann man zum Glück auch zeigen S.((M.) = M.−2 durch Induktion.[4]
In praktischen Implementierungen, insbesondere an Maschinen mit Shift-by-k und finde die erste Null Anweisungen kann die Leistung weiter verbessert werden, indem einmal auf ein Bit-Array umgeschaltet wird m gleich der Wortgröße (oder einem kleinen Vielfachen davon) erreicht wird. Da alle Operationen an einem einzelnen Wort eine konstante Zeit sind, wirkt sich dies nicht auf die asymptotische Leistung aus, vermeidet jedoch den Großteil des Zeigerspeichers und mehrere Zeiger-Dereferenzen, wodurch mit diesem Trick eine erhebliche praktische Zeit- und Raumersparnis erzielt wird.
Eine offensichtliche Optimierung von vEB-Bäumen besteht darin, leere Teilbäume zu verwerfen. Dies macht vEB-Bäume sehr kompakt, wenn sie viele Elemente enthalten, da keine Teilbäume erstellt werden, bis ihnen etwas hinzugefügt werden muss. Zu Beginn erstellt jedes hinzugefügte Element ungefähr Log(m) neue Bäume mit etwa m/ 2 Zeiger alle zusammen. Wenn der Baum wächst, werden immer mehr Teilbäume wiederverwendet, insbesondere die größeren. In einem vollen Baum von 2m nur Elemente O (2m) Platz wird genutzt. Darüber hinaus wird im Gegensatz zu einem binären Suchbaum der größte Teil dieses Speicherplatzes zum Speichern von Daten verwendet: Selbst für Milliarden von Elementen werden die Zeiger in einer vollständigen vEB-Baumnummer zu Tausenden.
Für kleine Bäume ist der mit vEB-Bäumen verbundene Overhead jedoch enorm: in der Größenordnung von
M.{ displaystyle { sqrt {M}}}. Dies ist ein Grund, warum sie in der Praxis nicht beliebt sind. Eine Möglichkeit, diese Einschränkung zu beheben, besteht darin, nur eine feste Anzahl von Bits pro Ebene zu verwenden, was zu einem Versuch führt. Alternativ kann jede Tabelle durch eine Hash-Tabelle ersetzt werden, wodurch der Speicherplatz auf reduziert wird Ö((n Log M.) (wo n ist die Anzahl der in der Datenstruktur gespeicherten Elemente) auf Kosten der Randomisierung der Datenstruktur. Es wurden andere Strukturen vorgeschlagen, einschließlich y-schneller Versuche und x-schneller Versuche, die vergleichbare Aktualisierungs- und Abfragezeiten aufweisen und auch zufällige Hash-Tabellen verwenden, um den Speicherplatz auf zu reduzieren Ö((n) oder Ö((n Log M.).
Siehe auch[edit]
Verweise[edit]
Weiterführende Literatur[edit]
Recent Comments