Splay-Tree
| Branch | Build status |
|---|---|
| master |  |
| develop |  |
In der Informatik ist ein Splay-Baum (auch Spreizbaum genannt, englisch Splay tree) ein spezieller Typ eines binären Suchbaums. Der Splay-Baum ist eine selbst-organisierende Datenstruktur mit der Besonderheit, dass die Organisation der gespeicherten Elemente sich potentiell nicht nur bei Modifikationen (wie bei AVL-Baum und Rot-Schwarz-Baum) ändert, sondern auch bei bloßen Anfragen. Die angefragten Elemente werden in die Nähe der Wurzel „gespült“, so dass sie bei einer alsbaldigen erneuten Suche schneller gefunden werden. Alle wichtigen Operationen wie Einfügen, Suchen und Löschen werden (amortisiert) effizient ausgeführt. Für eine gegebene Anfragesequenz verhält sich der Splay-Baum bezüglich der asymptotischen Laufzeit aller Anfragen äquivalent zu einer optimalen statischen Datenstruktur für diese Sequenz.[1] Diese Eigenschaft bezeichnet man als „statische Optimalität“. Es wird vermutet, dass die asymptotische Laufzeit der Anfragesequenz auch äquivalent zu der einer optimalen dynamischen Datenstruktur ist. Diese Vermutung ist als „dynamische Optimalität“ bekannt und gilt als eines der bekanntesten offenen Probleme auf dem Gebiet der Datenstrukturen [Quelle: Wikipedia].
Zick-Rotation
Zick-Zick-Rotation
Zack-Zick-Rotation
Suchen
Um ein Element zu suchen führt man eine Splay Operation auf das gesuchte Element aus welches somit an die Wurzel Position rotiert wird sofern es exsistiert.
Laufzeit: O(log n)
Einfügen
Um ein Element einem Splay Tree hinzufügen zu können geht man denn Baum solange hinunter (Schlüssel größer rechts und kleiner links) bis einer der unteren beiden Fälle eintritt:
- Element (Schlüssel) bereits vorhanden => Wert aktualisieren
- Element nicht vorhanden => Knoten an Stelle mit Schlüssel und Wert erstellen
Laufzeit: O(log n)
Löschen
Um ein Element zu löschen geht man solange hinunter bis man denn gewollten Schlüssel:
- findet, denn man dann löscht und dessen Unterbaum an denn Elternknoten anhängt und denn Elternknoten an die Wurzel rotiert
- nicht findet, wo nicht passiert
Laufzeit: O(log n)
Aufsplitten
Um einen Baum in zwei Hälften zu Teilen, an Knoten x, muss dieser zuvor in die Wurzel rotiert werden. Nun lässt sich
ein Verbindung zum Teilbaum trennen. Sollte nach dem splay(x, T) nicht x in der Wurzel stehen schneidet man die linke
hälft ab wenn x < y oder die rechte bei x >= y.
Laufzeit: O(log n)
Vereinigen
Vereinigt zwei Bäume die zuvor aufgeteilt wurden. Vor dem Vereinigen wird das maximalste Element x1 in T1 an die Wurzel
rotiert. Anschließend kann man T2 rechts an x1 problemlos anhängen.
Laufzeit: O(log n)
Nutzungshinweise:
Zur Nutzung der Splaytree implementierung kann der Code in ein Projekt eingebunden werden.
Dazu muss github.com/ob-algdatii-ss19/leistungsnachweis-the-gophers/splay importiert werden.
Neuen Baum erstellen
tree := splay.New()
Wert speichern
tree.Add(splay.Pair{Key: 1, Value: "value"})
Wert löschen
tree.Delete(1)
Wert auslesen
value := tree.Get(1)
Prüfen, ob Key im Baum gespeichert ist
contains := tree.Has(1)
Baum als String im JSON-Format
string := tree.String()
Eintrag mit minimalem Key abfragen
pair := tree.Minimum()
Eintrag mit maximalem Key abfragen
pair := tree.Maximum()
Baum aufsplitten
tree1, tree2, error := tree.Split(1)
Bäume zusammenfügen (Keys in Baum 1 müssen kleiner sein als Keys in Baum 2)
newTree := tree1.Join(tree2)