Linker Baum – Wikipedia
Prioritätswarteschlange implementiert mit einer Variante eines binären Heaps
In der Informatik, u linker Baum oder linker Haufen ist eine Prioritätswarteschlange, die mit einer Variante eines binären Heaps implementiert ist. Jeder Knoten x hat ein s-Wert das ist der Abstand zum nächsten Blatt im Teilbaum mit Wurzel x.[1] Im Gegensatz zu a binärer Haufen, versucht ein linker Baum, sehr unausgeglichen zu sein. Zusätzlich zur Heap-Eigenschaft werden linke Bäume beibehalten, sodass der rechte Nachkomme jedes Knotens den niedrigeren s-Wert hat.
Der höhenorientierte linke Baum wurde von Clark Allan Crane erfunden.[2] Der Name kommt daher, dass der linke Teilbaum normalerweise höher ist als der rechte Teilbaum.
Ein linker Baum ist ein zusammenfügbarer Haufen. Beim Einfügen eines neuen Knotens in einen Baum wird ein neuer Ein-Knoten-Baum erstellt und mit dem bestehenden Baum zusammengeführt. Um ein Element zu löschen, wird es durch die Zusammenführung seiner linken und rechten Unterbäume ersetzt. Beide Operationen benötigen O(log n) Zeit. Bei Einfügungen ist dies langsamer als bei Fibonacci-Heaps, die das Einfügen in O(1) (konstante) amortisierte Zeit unterstützen, und O(log n) schlimmsten Fall.
Linke Bäume sind aufgrund ihrer Fähigkeit zur schnellen Zusammenführung von Vorteil, im Vergleich zu binären Heaps, die Θ(n). In fast allen Fällen hat das Zusammenführen von Schrägstapeln eine bessere Leistung. Das Zusammenführen von linken Haufen hat jedoch den schlimmsten Fall O(log n) Komplexität beim Zusammenführen von schrägen Haufen hat sich nur O(log n) Komplexität.
Der übliche linke Baum ist a höhenabhängig linker Baum.[2] Es können jedoch auch andere Verzerrungen bestehen, wie z gewichtsabhängig linker Baum.[3]
S-Wert[edit]
Die s-Wert (oder Rang) eines Knotens ist die Entfernung von diesem Knoten zum nächsten Blatt im Teilbaum, der an diesem Knoten verwurzelt ist. Anders ausgedrückt, der s-Wert von a null Kind ist implizit null. Andere Knoten haben einen s-Wert gleich eins mehr als das Minimum der s-Werte ihrer Kinder. Im rechten Beispiel haben also alle Knoten mit mindestens einem fehlenden Kind einen s-Wert von 1, während Knoten 4 einen s-Wert von 2 hat, da sein rechtes Kind (8) einen s-Wert von 1 hat. (In einigen Beschreibungen wird der s-Wert von Null-Kindern mit –1 angenommen.[4])
Den kürzesten Weg zum nächsten fehlenden Blatt im Unterbaum kennen, der bei verwurzelt ist x ist genau von S(x), jeder Knoten in der Tiefe S(x)−1 oder weniger hat genau 2 Kinder, da S(x) wäre weniger gewesen, wenn nicht. Das bedeutet, dass die Größe des Baums mit Wurzeln bei x ist mindestens
2S(x)−1{displaystyle 2^{s(x)}-1}. Daher, S(x) ist höchstens
Protokoll(m+1){displaystyle log {(m+1)}}
, m die Anzahl der Knoten des Teilbaums mit Wurzel bei x.[1]
Operationen an einem höhenverzerrten linken Baum[1][edit]
Die meisten Operationen an einem höhenverzerrten linken Baum werden mit der Zusammenführungsoperation ausgeführt.
Zusammenführen von zwei Min HBLTs[edit]
Der Zusammenführungsvorgang nimmt zwei Min-HBLTs als Eingabe und gibt einen Min-HBLT zurück, der alle Knoten in den ursprünglichen Min-HBLTs zusammengenommen enthält.
Wenn entweder A oder B leer ist, gibt die Zusammenführung das andere zurück.
Im Fall von Min HBLTs nehmen wir an, dass wir zwei Bäume haben, die bei A und B verwurzelt sind, wobei A.key
≤{displaystyle leq}B.Taste. Andernfalls können wir A und B vertauschen, sodass die obige Bedingung gilt.
Die Zusammenführung erfolgt rekursiv durch Zusammenführen von B mit dem rechten Unterbaum von A. Dies könnte den S-Wert des rechten Unterbaums von A ändern. Um die Eigenschaft des linken Baums beizubehalten, prüfen wir nach jeder Zusammenführung, ob der S-Wert des rechten Teilbaums während der rekursiven Zusammenführungsaufrufe größer wurde als der S-Wert des linken Teilbaums. Wenn ja, vertauschen wir den rechten und linken Teilbaum (wenn ein Kind fehlt, sollte es das rechte sein).
Da wir davon ausgegangen sind, dass die Wurzel von A größer ist als die von B, wird auch die Heap-Eigenschaft beibehalten.
Pseudocode zum Zusammenführen von zwei min-Höhe voreingenommenen linken Bäumen[edit]
MERGE(A, B)
if A = null return B
if B = null return A
if A.key > B.key then
SWAP (A, B)
A.right := MERGE (A.right, B) // the result cannot be null since B is non-null
if A.left = null then
SWAP(A.left, A.right)
A.s_value := 1 // since the right subtree is null, the shortest path to a descendant leaf from node A is 1
return A
if A.right.s_value > A.left.s_value then
SWAP (A.right, A.left)
A.s_value := A.right.s_value + 1
return A
Java-Code zum Zusammenführen von zwei min-Höhen voreingenommenen linken Bäumen[edit]
public Node merge(Node x, Node y) {
if (x == null)
return y;
if (y == null)
return x;
// if this were a max-heap, then the
// next line would be: if (x.element < y.element)
if (x.element.compareTo(y.element) > 0) {
// x.element > y.element
Node temp = x;
x = y;
y = temp;
}
x.rightChild = merge(x.rightChild, y);
if (x.leftChild == null) {
// left child doesn't exist, so move right child to the left side
x.leftChild = x.rightChild;
x.rightChild = null;
// x.s was, and remains, 1
} else {
// left child does exist, so compare s-values
if (x.leftChild.s < x.rightChild.s) {
Node temp = x.leftChild;
x.leftChild = x.rightChild;
x.rightChild = temp;
}
// since we know the right child has the lower s-value, we can just
// add one to its s-value
x.s = x.rightChild.s + 1;
}
return x;
}
Beispiel[edit]
Ein Beispiel dafür, wie die Zusammenführungsoperation in einem linken Baum funktioniert, wird dargestellt. Die Kästchen stehen für jeden Zusammenführungsaufruf.
Wenn die Rekursion abgewickelt wird, tauschen wir linke und rechte Kinder aus, wenn x.right.s_value > x.left.s_value für jeden Knoten x. In diesem Fall haben wir die an Knoten wurzelnden Teilbäume mit den Schlüsseln 7 und 10 vertauscht.
Einfügen in ein Min HBLT[edit]
Das Einfügen erfolgt über den Zusammenführungsvorgang. Ein Einfügen eines Knotens in ein bereits bestehendes
Min HBLT, erstellt mit diesem Knoten einen HBLT-Baum der Größe eins und führt ihn mit dem vorhandenen Baum zusammen.
INSERT (A, x)
B := CREATE_TREE(x)
return MERGE(A, B)
Löschen des Min-Elements aus Min HBLT[edit]
Das Min-Element in einem Min-HBLT ist die Wurzel. Somit wird zum Löschen des Min die Wurzel gelöscht und ihre Unterbäume werden zusammengeführt, um die neue Min HBLT zu bilden.
DELETE_MIN(A)
x := A.key
A := MERGE (A.right, A.left)
return x
Initialisieren eines höhenverzerrten linken Baums[edit]
Das Initialisieren eines höhenverzerrten linken Baums erfolgt hauptsächlich auf eine von zwei Arten. Die erste besteht darin, jeden Knoten einzeln zu einem HBLT zusammenzuführen. Dieser Prozess ist ineffizient und dauert O(nlogn) Zeit. Der andere Ansatz besteht darin, eine Warteschlange zu verwenden, um jeden Knoten und den resultierenden Baum zu speichern. Die ersten beiden Elemente in der Warteschlange werden entfernt, zusammengeführt und wieder in die Warteschlange gestellt. Dies kann ein HBLT in O(n) Zeit. Dieser Ansatz wird in den drei mitgelieferten Diagrammen detailliert beschrieben. Ein linksgerichteter Baum mit minimaler Höhe wird angezeigt.
Um eine min HBLT zu initialisieren, stellen Sie jedes Element, das dem Baum hinzugefügt werden soll, in eine Warteschlange. Im Beispiel (siehe Teil 1 links) ist die Zahlenmenge [4, 8, 10, 9, 1, 3, 5, 6, 11] werden initialisiert. Jede Zeile des Diagramms stellt einen anderen Zyklus des Algorithmus dar, der den Inhalt der Warteschlange darstellt. Die ersten fünf Schritte sind einfach zu befolgen. Beachten Sie, dass das neu erstellte HBLT am Ende der Warteschlange hinzugefügt wird. Im fünften Schritt tritt das erste Auftreten eines s-Wertes größer als 1 auf. Der sechste Schritt zeigt zwei miteinander verschmolzene Bäume mit vorhersehbaren Ergebnissen.
In Teil 2 findet eine etwas komplexere Zusammenführung statt. Der Baum mit dem niedrigeren Wert (Baum x) hat ein rechtes Kind, daher muss merge erneut für den Teilbaum aufgerufen werden, der vom rechten Kind von Baum x und dem anderen Baum verwurzelt ist. Nach der Zusammenführung mit dem Teilbaum wird der resultierende Baum wieder in Baum x gestellt. Der s-Wert des rechten Kindes (s=2) ist jetzt größer als der s-Wert des linken Kindes (s=1), also müssen sie getauscht werden. Der s-Wert des Wurzelknotens 4 beträgt nun auch 2.
Teil 3 ist der komplexeste. Hier rufen wir merge zweimal rekursiv auf (jedes Mal mit dem nicht ausgegrauten Unterbaum des rechten untergeordneten Elements). Dies verwendet den gleichen Prozess, der für Teil 2 beschrieben wurde.
Löschen eines beliebigen Elements aus einem Min HBLT[edit]
Wenn wir einen Zeiger auf einen Knoten x in einem Min HBLT haben, können wir ihn wie folgt löschen: Ersetzen Sie den Knoten x durch das Ergebnis der Zusammenführung seiner beiden Teilbäume und aktualisieren Sie die s-Werte der Knoten auf dem Pfad von x zur Wurzel , Vertauschen des rechten und linken Teilbaums, falls erforderlich, um die Eigenschaft des linken Baums beizubehalten.
Die Aufwärtstraversierung wird fortgesetzt, bis entweder wir die Wurzel treffen oder sich die s-Werte nicht ändern. Da wir ein Element löschen, können die S-Werte auf dem zurückgelegten Weg nicht erhöht werden. Jeder Knoten, der bereits das rechte Kind seines Elternteils ist und bewirkt, dass der s-Wert seines Elternteils verringert wird, bleibt auf der rechten Seite. Jeder Knoten, der das linke Kind seines Elternteils ist und bewirkt, dass der s-Wert des Elternteils verringert wird, muss mit seinem rechten Geschwister vertauscht werden, wenn der s-Wert kleiner wird als der aktuelle s-Wert des rechten Kindes.
Jeder Knoten muss einen Zeiger auf seinen Elternknoten haben, damit wir den Pfad zur Wurzel durchlaufen können, um die S-Werte zu aktualisieren.
Wenn die Durchquerung an einem Knoten y endet, liegen die durchlaufenen Knoten alle auf dem am weitesten rechts liegenden Pfad, der bei Knoten y verwurzelt ist. Ein Beispiel ist unten gezeigt. Daraus folgt, dass die Anzahl der durchlaufenen Knoten höchstens log(m) beträgt, wobei m die Größe des bei y wurzelnden Teilbaums ist. Somit benötigt diese Operation auch O(lg m) zur Durchführung.
Gewichtungsverzerrter linker Baum[5][edit]
Linke Bäume können auch gewichtsverzerrt sein. Anstatt s-Werte in Knoten x zu speichern, speichern wir in diesem Fall ein Attribut w(x) bezeichnet die Anzahl der Knoten im Unterbaum mit Wurzel bei x:
w(x) = w(x.rechts) + w(x.links) + 1
WBLTs stellen w(x.left) ≥ w(x.right) für alle internen Knoten x sicher. WBLT-Operationen stellen diese Invariante sicher, indem sie die Kinder eines Knotens vertauschen, wenn der rechte Teilbaum aus dem linken herauswächst, genau wie bei HBLT-Operationen.
Zusammenführen von zwei Min WBLTs[edit]
Die Zusammenführungsoperation in WBLTs kann unter Verwendung einer einzigen Durchquerung von oben nach unten durchgeführt werden, da die Anzahl der Knoten in den Unterbäumen vor dem rekursiven Aufruf zum Zusammenführen bekannt ist. Somit können wir linke und rechte Teilbäume vertauschen, wenn die Gesamtzahl der Knoten im rechten Teilbaum und dem zu verschmelzenden Baum größer ist als die Anzahl der Knoten im linken Teilbaum. Dies ermöglicht die Durchführung der Operationen in einem einzigen Pfad und verbessert so die Zeitkomplexität der Operationen um einen konstanten Faktor.
Der Zusammenführungsvorgang ist in der folgenden Grafik dargestellt.
Andere Operationen auf WBLT[edit]
Das Einfügen und Löschen des min-Elements kann wie bei HBLTs mit dem Zusammenführungsvorgang erfolgen.
Obwohl WBLTs HBLTs beim Zusammenführen, Einfügen und Löschen des Min-Schlüssels um einen konstanten Faktor übertreffen, Ö(Protokoll n) ist beim Löschen eines beliebigen Elements aus WBLTs nicht garantiert, da θ(n) Knoten müssen durchlaufen werden.
Wenn dies ein HBLT wäre, würde das Löschen des Blattknotens mit Schlüssel 60 dauern Ö(1) Zeit und Aktualisierung der s-Werte werden nicht benötigt, da sich die Länge des ganz rechten Pfads für alle Knoten nicht ändert.
Aber in einem WBLT-Baum müssen wir die Gewichtung jedes Knotens zurück auf die Wurzel aktualisieren, was Ö(n) schlimmsten Fall.
Varianten[edit]
Es gibt mehrere Variationen des grundlegenden linken Baums, die nur geringfügige Änderungen am grundlegenden Algorithmus vornehmen:
- Die Wahl des linken Kindes als das größere ist willkürlich; ein “rechter Baum” würde genauso gut funktionieren.
- Es ist möglich, den Austausch von Kindern zu vermeiden, sondern stattdessen aufzunehmen welcher child ist der höchste Wert (z. B. das niedrigstwertige Bit des s-Werts) und verwenden Sie diesen in der Zusammenführungsoperation.
- Der s-Wert, der verwendet wird, um zu entscheiden, mit welcher Seite zusammengeführt werden soll, könnte eine andere Metrik als die Höhe verwenden. Zum Beispiel könnte das Gewicht (Anzahl der Knoten) verwendet werden.
Verweise[edit]
- ^ ein B C “Linke Bäume” (PDF). www.google.com. Abgerufen 2019-05-31.
- ^ ein B Kran, Clark A. (1972), Lineare Listen und Prioritätswarteschlangen als ausgeglichene Binärbäume (Doktorarbeit), Department of Computer Science, Stanford University, ISBN 0-8240-4407-X, STAN-CS-72-259
- ^ Seonghun-Cho; Sartaj Sahni (1996), “Gewichtsverzerrte linke Bäume und modifizierte Skip-Listen” (PDF), Zeitschrift für experimentelle Algorithmik, 3, CiteSeerX 10.1.1.13.2962, doi:10.1145/297096.297111
- ^ Stewart, James (25. September 1988). “LINKE BÄUME”. Dynamisches Grafikprojekt der Universität Toronto. Abgerufen 2019-05-31.
- ^ Cho, Seonghun; Sahni, Sartaj (September 1998). “Gewichtsabhängige linke Bäume und modifizierte Skip-Listen”. J. Erw. Algorithmen. 3. mach:10.1145/297096.297111. ISSN 1084-6654.
Recent Comments