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.

Splay-Bäume wurden 1985 von Daniel Sleator und Robert Tarjan unter dem Namen Self-Adjusting Binary Search Trees vorgestellt.[1]

Operationen

Bearbeiten

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.

Wird die Splay-Operation auf ein Element   in einem Baum   angewendet, so sorgt sie dafür, dass   nach der Operation in der Wurzel von   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   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   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   die neue Wurzel des Baumes und die Splay-Operation beendet. Liegt   im rechten Teilbaum seines Vaters, wird analog eine zack-Rotation (Links-Rotation) durchgeführt. Hat   einen Großvater, so können zwei Einzelrotationen zu einer Kompositrotation zusammengesetzt werden.

 

Zick-Zick-Rotation

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

 

Zack-Zick-Rotation

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

 

Amortisierte Laufzeit:  

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

Amortisierte Laufzeit:  

Einfügen

Bearbeiten

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

  wird mit   verglichen:

wenn   größer als  , dann wird   mit seinem linken Teilbaum   links an   angehängt. Der rechte Teilbaum   wird rechts an   angehängt.
wenn   kleiner als  , dann wird   mit seinem rechten Teilbaum   rechts an   angehängt. Der linke Teilbaum   wird links an   angehängt.

Somit ist   an der Wurzel und an der richtigen Stelle.

Amortisierte Laufzeit:  

Löschen

Bearbeiten

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

Amortisierte Laufzeit:  

Vereinigen

Bearbeiten

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

Amortisierte Laufzeit:  

Aufsplitten

Bearbeiten

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

Amortisierte Laufzeit:  

Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b 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]).