Einleitung

Wie schon in früheren Kapiteln sollen binäre Suchbäume verwendet werden, um Elemente, bestehend aus einem Schlüssel und einer Information, anhand ihres Schlüssels zu lokalisieren. Das Universum ist total geordnet, und innerhalb eines Suchbaumes soll die Invariante ``Knoten im lUb $\leq$ Key(Wurzel) $\leq$ Knoten im rUb`` gelten.
Der hier zugrundeliegende Ansatz bemüht sich, innerhalb einer Folge von Operationen durch Realzeit-Umorganisation der Datenstruktur möglichst weit vom worst-case zu entfernen, statt die jeweiligen worst-case-Kosten zu minimieren. Bei jedem Zugriff auf den Baum soll eine möglichst einfache Reorganisationsregel angewendet werden, um die Laufzeit künftiger Operationen zu vermindern. Wie bei der MFR für selbst organisierende Listen soll erreicht werden, daß Elemente mit häufigem Zugriff möglichst nahe an der Wurzel liegen. Ein Element, auf das die Suchoperation angewendet wird, wird zur Wurzel befördet, in der i.a. berechtigten Hoffnung, daß weitere Zugriffe auf dieses Element folgen.

Definition: Ein Splay-Tree ist ein interner binärer Suchbaum, d.h.

• ``Knoten im lUb $\leq$ Key(Wurzel) $\leq$ Knoten im rUb``
• Alle Knoten tragen Elemente, denn Zeiger auf Blätter sind NIL-Pointer.

Rotationen, um Knoten an die Wurzel zu bewegen.
Beispiele:

i)

Einfach Rotation

ii)

Move to root

Beide Heuristiken benötigen für geeignete Folgen von Zugriffsoperationen $\Omega$(n) amortisierte Zeit. Beim MTR (Move To Root) im probabilistischen Sinn ist dies eine gute Komplexität. Zugriffswahrscheinlichkeiten sind fest und unabhängig.