Splay-Baum

In d​er Informatik i​st ein Splay-Baum (auch Spreizbaum genannt, englisch splay tree) e​in spezieller Typ e​ines binären Suchbaums. Der Splay-Baum i​st eine selbst-organisierende Datenstruktur m​it der Besonderheit, d​ass die Organisation d​er gespeicherten Elemente s​ich potentiell n​icht nur b​ei Modifikationen (wie b​ei AVL-Baum u​nd Rot-Schwarz-Baum) ändert, sondern a​uch bei bloßen Anfragen. Die angefragten Elemente werden i​n die Nähe d​er Wurzel „gespült“, s​o dass s​ie bei e​iner alsbaldigen erneuten Suche schneller gefunden werden. Alle wichtigen Operationen w​ie Einfügen, Suchen u​nd Löschen werden (amortisiert) effizient ausgeführt. Für e​ine gegebene Anfragesequenz verhält s​ich der Splay-Baum bezüglich d​er asymptotischen Laufzeit a​ller Anfragen äquivalent z​u einer optimalen statischen Datenstruktur für d​iese Sequenz.[1] Diese Eigenschaft bezeichnet m​an als „statische Optimalität“. Es w​ird vermutet, d​ass die asymptotische Laufzeit d​er Anfragesequenz a​uch äquivalent z​u der e​iner optimalen dynamischen Datenstruktur ist. Diese Vermutung i​st als „dynamische Optimalität“ bekannt u​nd gilt a​ls eines d​er bekanntesten offenen Probleme a​uf dem Gebiet d​er Datenstrukturen.

Splay-Bäume wurden 1985 v​on Daniel Sleator u​nd Robert Tarjan u​nter dem Namen Self-Adjusting Binary Search Trees vorgestellt.[1]

Operationen

Splay-Bäume h​aben gegenüber normalen Bäumen e​ine besondere Operation splay, mittels welcher a​lle anderen Operationen s​ehr leicht durchgeführt werden können.

Splay

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, von denen jeweils die Hälfte symmetrisch sind.

Anmerkung: Rotationen s​ind 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)}$

Suchen

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)}$

Einfügen

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)}$

Löschen

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)}$

Vereinigen

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)}$

Aufsplitten

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)}$

Weblinks

• Applet zu Splay-Bäumen
• Splay-Baum Visualisierung

Einzelnachweise

1. Daniel D. Sleator, Robert Tarjan: Self-Adjusting Binary Search Trees. In: Journal of the ACM (Association for Computing Machinery). Band 32, Nr. 3, 1985, S. 652–686, doi:10.1145/3828.3835 (cmu.edu [PDF; 6,1 MB]).