WikiDer > Spreizboom
EIN Baumspiel spielen ist ein selbstausgleichendes Binärer Suchbaum, mit der zusätzlichen Funktion, dass häufig besuchte Knospen näher an der Wurzel sind (und somit schneller gefunden werden). Standardoperationen wie das Hinzufügen, Suchen und Entfernen eines Kreisels werden in . ausgeführt Auf) Zeit für eine Operation, aber amortisiert in O(log(n)) Zeit für eine Reihe von n Operationen. Für viele nicht (völlig) zufällige Sequenzen von Operationen übertreffen Splay Trees die Standard-Binärdatei Bäume suchen, insbesondere wenn eine relativ kleine Teilmenge der Spitzen des Baums häufig besucht wird.Alle Operationen an einem Spreizbaum werden wie in einer normalen Binärdatei ausgeführt Suchbaum, aber es folgt ein Spreizschritt. Der Spreizbaum wurde entwickelt von Daniel Sleator und Robert Tarjan
Von unten nach oben und von oben nach unten
Beim Ausbreiten von "Bottom-Up" wird die Operation ausgeführt und gleichzeitig der Weg zum besuchten Top verfolgt. Nachdem die Bearbeitung abgeschlossen ist, wird der Pfad vollständig von unten nach oben gespreizt. Um den Pfad zu speichern, wird oft eine Stack-Datenstruktur verwendet, bei der die letzten 3 Vertices von pop() für den Splay-Schritt gepoppt werden und die neue Wurzel dieses Unterbaums mit diesen 3 Vertices an den Stack zurückgegeben wird push()'t .
Wenn "Top-Down" gespreizt wird, werden immer wenn 3 Ebenen (Oberseiten) absteigen, diese 3 Obergrenzen gespreizt. Das letzte Top wird auch wiederverwendet, um den Teilbaum mit den nächsten 3 Tops zu konstruieren.
Top-Down-Implementierungen sind daher typischerweise etwa doppelt so schnell wie Bottom-Up-Implementierungen, da nicht der gesamte Pfad zum letzten Top erst aufgebaut und dann zum Spreizen komplett fertig gestellt werden muss.
Der Spreizschritt
Der Pfad wird so lang wie möglich pro 3 Kreisel gespreizt (der letzte Kreisel x, sein Elternteil p und der Elternteil von p, genannt g), nur wenn am Ende nur 2 Kreisel verfügbar sind, kann mit 2 Kreiseln gespreizt werden (dies ist nur wenn der (vollständige) Pfad zum gesuchten Element im Baum eine gerade Anzahl von Spitzen enthält) Es sind insgesamt 6 Fälle zu unterscheiden, "zig-zig", "zig-zag", "zig" und ihre Spiegelbilder" zag-zag", "zag-zig" und "zag". Wir besprechen nur die ersten 3, die anderen sind völlig analog:
zig-zig Schritt: Hier ist x ein linkes Kind von p und p ist ein linkes Kind von g. Nennen wir das linke Kind von x b1, das rechte Kind von x b2, das rechte Kind von p b3 und das rechte Kind von g b4 Nun machen wir x zur neuen Wurzel, b1 bleibt ein linkes Kind von x und p wird zum neuen rechtes Kind von x. g wird das neue rechte Kind von p. Das neue linke Kind von p ist b2 und das neue linke Kind von g ist b3. b4 bleibt das rechte Kind von g.
Zickzack Schritt: Hier ist x ein rechtes Kind von p und p ist ein linkes Kind von g. Nennen Sie das linke Kind von p b1, das linke Kind von x b2, das rechte Kind von x b3 und das rechte Kind von g b4 Nun machen wir x zur neuen Wurzel, p wird zum linken Kind von x und g wird zum rechten Kind von x. b1 bleibt das linke Kind von p, b2 wird das rechte Kind von p, b3 wird das linke Kind von g und b4 bleibt das rechte Kind von g.
zig Schritt: hier gibt es kein g, nur ein Elternteil p mit dem linken Kind x. Nennen Sie das linke Kind von x b1, das rechte Kind von x b2 und das rechte Kind von p b3. Wir machen x zur neuen Wurzel, b1 bleibt das linke Kind von x und b3 bleibt das rechte Kind von p, aber das neue linke Kind von x ist p und das neue rechte Kind von p ist b2.
Beachten Sie, dass die äußeren Bäume des Unterpfads von 2 oder 3 Knoten (d. h. Unterbäume des 'großen' Baums mit Wurzeln b1, b2, b3 und b4) auch NULL sein können, dh es spielt keine Rolle, ob x ein Blatt ist oder 1 . hat oder 2 Kinder.
halb spielen
Eine kleine Variante des Spreizens ist dieses Semi-Spreizen, bei dem die besuchte Spitze nicht die Wurzel des Spreizbaums werden kann, wenn beim Spreizen des Pfades eine Zick-Zick- oder Zick-Zack-Operation durchgeführt wurde. Der Unterschied zur Standardspreizung besteht in diesem Vorgang:
zig-zig Schritt: hier ist x ein linkes Kind von o und o ein linkes Kind von g. Nennen wir das linke Kind von x b1, das rechte Kind von x b2, das rechte Kind von o b3 und das rechte Kind von g b4 Nun machen wir o zur neuen Wurzel, x bleibt ein linkes Kind von o, aber g wird zum neuen rechtes Kind von o. b1 und b2 bleiben die Kinder von x, aber b3 und b4 werden die Kinder von g.
Externe Links
Der Algorithmus
- "Self-adjusting Binary Search Trees", Sleator und Tarjan (der Originalartikel von 1985)
- NISTs "Dictionary of Algorithms and Data Structures" im "Splay Tree"
Implementierungen
- Implementierungen in C und Java von Sleator (einer der Autoren)
- Header-Datei von FreeBSDD
- NGenerics : Implementierung in C#