Splay Trees

Definition:
Ein Splay Tree ist ein interner binärer Suchbaum mit Move-To-Root-Heuristik.

Definition:
Die Move-To-Root-Heuristik (MTR) bewirkt bei jedem Zugriff ''Splay'' auf ein Element, dass es anhand von Rotationen (zig, zig-zig, zig-zag) zur Wurzel befördert wird.

Rotationen: ($p$ soll an die Wurzel, sei $q$ Vater und $r$ Großvater)
Fall 1 ''zig'': $q$ ist Wurzel
Fall 2 ''zig-zig'': $p$ und $q$ sind beides rechte oder beides linke Söhne
Fall 3 ''zig-zag'': von $p$ und $q$ ist je einer linker und einer rechter Sohn

Operationen:

1. $Splay(k,T)$: von der Wurzel den Baum bis zum Element mit Schlüssel $k$ traversieren (bzw. zum nächstkleineren Element), dann das Element an die Wurzel rotieren

2. $Find(k,T)$: Splay und Element ausgeben (falls ein Element mit Schlüssel $k$ existiert)

3. $Split(k,T)$: Splay und in zwei Teilbäume mit Schlüssel $\leq k$ und $> k$ zerlegen, dazu an der Wurzel den rechten Teilbaum abspalten

4. $Insert(x,T)$: Split bei $key[x]$ und Teilbäume an Wurzel $x$ hängen. Vorsicht: der Splay Tree entartet beim Einfügen vorsortierter Elemente

5. $Join(T_1,T_2)$: größtes Element in $T_1$ mit Splay an die Wurzel und $T_2$ einhängen

6. $Delete(x,T)$: $x$ mit Splay an die Wurzel und entfernen, dann Join der beiden Teilbäume

Definitionen:
- $size(v)$ ist Anzahl der Knoten im Teilbaum mit Wurzel $v$
- $\phi(v) := \log(size(v))$ ist Potential von $v$
- $\Phi(T) := \sum_{v \in T} \phi(v)$ ist Potential des Baumes

Analyse:
- Amortisierte Laufzeit einer Splay-Operation ist
$3(\phi_{nach}(x) - \phi_{vor}(x))$ in den Fällen 1 und 2
$3(\phi_{nach}(x) - \phi_{vor}(x))+1$ im Fall 3
- Jeweils $k$ beliebige Operationen haben Worst Case Laufzeit $O(k \log n)$