Splay-Baum

Wird die Splay-Operation auf ein Element ${\displaystyle x}$ in einem Baum ${\displaystyle T}$ angewendet, so sorgt sie dafür, dass ${\displaystyle x}$ nach der Operation in der Wurzel von ${\displaystyle 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 ${\displaystyle x}$ jeweils mit seinem Vater bzw. Großvater verglichen. Aufgrund dieses Vergleiches werden insgesamt sechs Fälle unterschieden, die jeweils paarweise symmetrisch sind.

Anmerkung: Rotationen sind im Artikel Binärbaum beschrieben.

Zick-Rotation

Falls ${\displaystyle 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 ${\displaystyle x}$ die neue Wurzel des Baumes und die Splay-Operation beendet. Liegt ${\displaystyle x}$ im rechten Teilbaum seines Vaters, wird analog eine zack-Rotation (Links-Rotation) durchgeführt. Hat ${\displaystyle x}$ einen Großvater, so können zwei Einzelrotationen zu einer Kompositrotation zusammengesetzt werden.

Zick-Zick-Rotation

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

Zack-Zick-Rotation

Ist ${\displaystyle 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 ${\displaystyle x}$ die Position mit seinem Großvater und alle weiteren Unterbäume werden an die entsprechenden Stellen gesetzt. Falls ${\displaystyle x}$ nach der Rotation noch nicht in der Wurzel des Baumes steht, so wird weiterrotiert. Symmetrisch hierzu die zick-zack-Rotation, falls ${\displaystyle x}$ das linke Kind seines Vaters ist, welcher das rechte Kind des Großvaters von ${\displaystyle x}$ ist.

Amortisierte Laufzeit: ${\displaystyle O(\log n)}$

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

Amortisierte Laufzeit: ${\displaystyle O(\log n)}$

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

${\displaystyle x}$ wird mit ${\displaystyle v}$ verglichen:

wenn ${\displaystyle x}$ größer als ${\displaystyle v}$, dann wird ${\displaystyle v}$ mit seinem linken Teilbaum ${\displaystyle T_{1}}$ links an ${\displaystyle x}$ angehängt. Der rechte Teilbaum ${\displaystyle T_{2}}$ wird rechts an ${\displaystyle x}$ angehängt.

wenn ${\displaystyle x}$ kleiner als ${\displaystyle v}$, dann wird ${\displaystyle v}$ mit seinem rechten Teilbaum ${\displaystyle T_{2}}$ rechts an ${\displaystyle x}$ angehängt. Der linke Teilbaum ${\displaystyle T_{1}}$ wird links an ${\displaystyle x}$ angehängt.

Somit ist ${\displaystyle x}$ an der Wurzel und an der richtigen Stelle.

Amortisierte Laufzeit: ${\displaystyle O(\log n)}$

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

Amortisierte Laufzeit: ${\displaystyle O(\log n)}$

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

Amortisierte Laufzeit: ${\displaystyle O(\log n)}$

Um einen Splay-Baum ${\displaystyle T}$ bei dem Knoten ${\displaystyle x}$ in zwei Splay-Bäume aufzusplitten, macht man zuerst ${\displaystyle x}$ mittels splay zur Wurzel von ${\displaystyle T}$. War ${\displaystyle 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 ${\displaystyle y}$ in der Wurzel, so war ${\displaystyle x}$ selbst nicht in ${\displaystyle T}$ enthalten. Ist ${\displaystyle x}$ nun kleiner als ${\displaystyle y}$, so kann man das linke Kind von ${\displaystyle y}$ abschneiden, andernfalls sein rechtes.

Amortisierte Laufzeit: ${\displaystyle O(\log n)}$