Splay-Baum

In der Informatik ist ein Splay-Baum (auch Spreizbaum genannt, englisch Splay tree) eine baumartige Datenstruktur zum Verwalten verschiedener Elemente. Die Besonderheit von Splay-Bäumen ist, dass sie erwartet balanciert sind, wodurch alle wichtigen Operationen wie Einfügen, Suchen und Löschen effizient ausgeführt werden können. Splay-Bäume wurden 1985 von Daniel Sleator und Robert Tarjan unter dem Namen Self-Adjusting Binary Search Trees vorgestellt.

Operationen

Splay-Bäume haben gegenüber normalen Bäumen eine besondere Operation splay, mittels welcher alle anderen Operationen sehr leicht durchgeführt werden können.

Splay

Wird die Splay-Operation auf ein Element x in einem Baum T angewendet, so sorgt sie dafür, dass x nach der Operation in der Wurzel von T steht. Dies wird erreicht, indem das Element Schritt für Schritt im Baum hinaufrotiert wird, bis es schließlich bei der Wurzel angekommen ist. Hierzu wird x jeweils mit seinem Vater bzw. Großvater verglichen. Aufgrund dieses Vergleiches werden insgesamt sechs Fälle unterschieden, von denen jeweils die Hälfte symmetrisch sind.

Anmerkung: Rotationen sind im Artikel Binärbaum beschrieben.

Zick-Rotation

Falls x das linke Kind seines Vaters ist und keinen Großvater hat, und somit bereits direkt unter der Wurzel steht, wird eine zick-Rotation (Rechts-Rotation) durchgeführt. Nun ist x die neue Wurzel des Baumes und die Splay-Operation beendet. Liegt x im rechten Teilbaum seines Vaters, wird analog eine zack-Rotation (Links-Rotation) durchgeführt. Hat x einen Großvater, so können zwei Einzelrotationen zu einer Kompositrotation zusammengesetzt werden.

Zick-Zick-Rotation

Ist x das linke Kind seines Vaters, welcher das linke Kind des Großvaters von x ist, so wird eine zick-zick-Rotation (zwei Rechts-Rotationen) durchgeführt. Hierbei wird x mit dem Großvater vertauscht und alle weiteren Unterbäume werden an die entsprechenden Stellen gesetzt. Falls x nach der Rotation noch nicht in der Wurzel des Baumes steht, so wird weiterrotiert. Symmetrisch hierzu die zack-zack-Rotation, falls x das rechte Kind seines Vaters ist, welcher das rechte Kind des Großvaters von x ist.

Zack-Zick-Rotation

Ist x das zweite Kind (von links) seines Großvaters, so wird eine zack-zick-Rotation (Links-Rotation gefolgt von einer Rechts-Rotation) durchgeführt. Hierbei tauscht x die Position mit seinem Großvater und alle weiteren Unterbäume werden an die entsprechenden Stellen gesetzt. Falls x nach der Rotation noch nicht in der Wurzel des Baumes steht, so wird weiterrotiert. Symmetrisch hierzu die zick-zack-Rotation, falls x das linke Kind seines Vaters ist, welcher das rechte Kind des Großvaters von x ist.

Amortisierte Laufzeit: O(log n)

Suchen

Um ein Element x im Baum T zu suchen, führt man einfach splay(x,T) aus. Dies bewirkt, dass falls x in T enthalten war, es nun in der Wurzel steht. Somit muss man nur noch die neue Wurzel mit x vergleichen. Sind sie unterschiedlich, war x nicht im Baum.

Amortisierte Laufzeit: O(log n)

Einfügen

Um ein Element x in einen Splay-Baum T einzufügen, sucht man zuerst wie in einem Binärbaum nach x. Nachdem diese Suche erfolglos endet, bekommt man den Knoten v, an dem x angehängt werden müsste. Dieser Knoten v wird jetzt mit der splay-Operation an die Wurzel gebracht. Somit ist v nun an der Wurzel und hat zwei Teilbäume T1 und T2. Jetzt wird die split-Operation ausgeführt:

x wird mit v verglichen:

wenn x größer als v, dann wird v mit seinem linken Teilbaum T1 links an x angehängt. Der rechte Teilbaum T2 wird rechts an x angehängt.

wenn x kleiner als v, dann wird v mit seinem rechten Teilbaum T2 rechts an x angehängt. Der linke Teilbaum T1 wird links an x angehängt.

Somit ist x an der Wurzel und an der richtigen Stelle.

Amortisierte Laufzeit: O(log n)

Löschen

Um x aus T zu löschen, führt man erst einmal eine Suche auf x aus, wird das Element gefunden, wird es gelöscht, und der Unterbaum an den Elternknoten P(x) angehängt. Gefolgt von splay(P(x), T), welches den Elternknoten in die Wurzel holt.

Amortisierte Laufzeit: O(log n)

Vereinigen

Die Operation join vereinigt zwei Splay-Bäume T₁ und T₂, welche unmittelbar vorher mittels split getrennt wurden. Hierbei wird zuerst mittels splay(∞,T₁) das maximale Element x₁ des ersten Baumes gesucht und in die Wurzel rotiert. Da die beiden Bäume T₁ und T₂ das Ergebnis einer vorherigen split-Operation sind, sind alle Elemente in T₂ größer als die Elemente in T₁, weswegen man den Baum T₂ nun ohne Probleme zum rechten Kind von x₁ machen kann.

Amortisierte Laufzeit: O(log n)

Aufsplitten

Um einen Splay-Baum T bei dem Knoten x in zwei Splay-Bäume aufzusplitten, macht man zuerst x mittels splay zur Wurzel von T. War x im Baum enthalten, kann man nun die Verbindung zu einem der beiden Teilbäume einfach trennen. Steht nach der Splay-Operation ein anderes Element y in der Wurzel, so war x selbst nicht in T enthalten. Ist x nun kleiner als y, so kann man das linke Kind von y abschneiden, andernfalls sein rechtes.

Amortisierte Laufzeit: O(log n)

Literatur

• D.D. Sleator and R.E. Tarjan. Self-Adjusting Binary Search Trees. Journal of the ACM 32:3, S. 652-686, 1985.

Weblinks

• Applet zu Splay-Bäumen