imported>SchlurcherBot: Bot: http → https

2025-09-22T08:16:25Z

Bot: http → https

Neue Seite

In der Informatik ist ein '''Splay-Baum''' (auch Spreizbaum genannt, englisch ''splay tree'') ein spezieller Typ eines [[binärer Suchbaum|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 [[Gewurzelter Baum|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 ([[Amortisierte Laufzeitanalyse|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.<ref name="SleatorTarjan">{{Literatur |Autor=Daniel D. Sleator, [[Robert E. Tarjan|Robert Tarjan]] |Titel=Self-Adjusting Binary Search Trees |Sammelwerk=Journal of the ACM ([[Association for Computing Machinery]]) |Band=32 |Nummer=3 |Datum=1985 |Seiten=652–686 |Online=https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf |Format=PDF |KBytes=6100 |DOI=10.1145/3828.3835}}</ref> 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.

Splay-Bäume wurden 1985 von [[Daniel Sleator]] und [[Robert Tarjan]] unter dem Namen ''Self-Adjusting Binary Search Trees'' vorgestellt.<ref name="SleatorTarjan" />

== 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 <math>x</math> in einem Baum <math>T</math> angewendet, so sorgt sie dafür, dass <math>x</math> nach der Operation in der Wurzel von <math>T</math> 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 <math>x</math> 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#Rotation in binären Bäumen|Binärbaum]] beschrieben.

'''Zick-Rotation'''

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

[[Datei:splay tree zig.svg|center|340px]]

'''Zick-Zick-Rotation'''

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

[[Datei:zigzig.gif|center]]

'''Zack-Zick-Rotation'''

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

[[Datei:zigzag.gif|center]]

'''Amortisierte Laufzeit:''' <math>O(\log n)</math>

=== Suchen ===

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

'''Amortisierte Laufzeit:''' <math>O(\log n)</math>

=== Einfügen ===

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

<math>x</math> wird mit <math>v</math> verglichen:

:wenn <math>x</math> größer als <math>v</math>, dann wird <math>v</math> mit seinem linken Teilbaum <math>T_1</math> links an <math>x</math> angehängt. Der rechte Teilbaum <math>T_2</math> wird rechts an <math>x</math> angehängt.

:wenn <math>x</math> kleiner als <math>v</math>, dann wird <math>v</math> mit seinem rechten Teilbaum <math>T_2</math> rechts an <math>x</math> angehängt. Der linke Teilbaum <math>T_1</math> wird links an <math>x</math> angehängt.

Somit ist <math>x</math> an der Wurzel und an der richtigen Stelle.

'''Amortisierte Laufzeit:''' <math>O(\log n)</math>

=== Löschen ===

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

'''Amortisierte Laufzeit:''' <math>O(\log n)</math>

=== Vereinigen ===

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

'''Amortisierte Laufzeit:''' <math>O(\log n)</math>

=== Aufsplitten ===

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

'''Amortisierte Laufzeit:''' <math>O(\log n)</math>

== Weblinks ==

* [https://www.cs.usfca.edu/~galles/visualization/SplayTree.html Splay-Baum Visualisierung]

== Einzelnachweise ==
<references />

[[Kategorie:Suchbaum]]

Splay-Baum - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https