# 13 Splay-Bäume

[TOC]

[comment]: # (Zuerst ein paar LaTeX-Makros:)

$\newcommand{\N}{\mathbb{N}}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\O}{\mathcal{O}}$

*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).

## Einführung

Wir haben uns in den letzten Stunden damit beschäftigt, wie wir Datenstrukturen auf bekannte Zugriffsmuster hinzuoptimieren.

Bei linearen Listen und vorab bekannte Häufigkeiten haben wir gesehen, dass dies ganz einfach geht: Wir sortieren die Elemente in absteigender Zugriffshäufigkeit. Für binäre Suchbäume haben wir gestern gesehen, dass wir mittels dynamischer Programmierung die statisch optimale Struktur ebenfalls finden können.

Mit der *Move-to-Front*-Regel haben wir gezeigt, dass wir mit selbstanordnenden linearen Listen auch bei dynamischen Zugriffen gut abschneiden können. Was nun also noch fehlt: Können wir uns das auch für binäre Suchbäume überlegen?

## Selbstanordnung in Suchbäumen

### Move-to-Root
Was wäre das Analoge zu *Move-to-Front* in einem Suchbaum? Wir greifen auf ein Element zu und wollen dabei die Datenstruktur so anpassen, dass danach der erneute Zugriffe nur noch $1$ kostet.

Nachdem wir ein Element zugegriffen habe, legen wir es an die Wurzel. So wird der nächste Zugriff auf dieses Element nur $1$ kosten.

Wie führt man ein solches *Move-to-Root* in einem Suchbaum durch? Wir können das Element `x` nicht einfach rausschneiden und oben einsetzen und auch ein Vertauschen mit der Wurzel ist problematisch, da dabei potentiell die Suchbaumeigenschaft zerstört wird. Wie können wir `x` hochblubbern lassen? Was für eine Operation kennen wir, die Schlüssel umgruppiert ohne die Suchbaumeigenschaft zu verletzen? Die Rotation!

Wir rotieren also `x` von unten zur Wurzel hin nach oben. Egal wo der Schlüssel `x` liegt, können wir ihn dem Suchpfad entlang immer zur Wurzel hochrotieren.


Wir interessieren uns dafür, wie sich das über eine Folge von Zugriffsoperationen entwickelt. Eine einzelne Operation darf durchaus lange dauern, aber was ist im Schnitt? Es kann uns also nur eine amortisierte Analyse helfen.

Wir sehen leicht, dass *Move-to-Root* für eine Folge von Operationen nicht effizient ist, indem wir eine Folge angeben, die in jedem Zugriff Kosten $\Theta(n)$ hat.

Wir starten mit einem Baum in der Form einer linearen Liste und greifen wiederholt auf das unterste Element zu. Das Hochrotieren belässt die Gestalt in der Form einer linearen Liste, weshalb wir Gesamtkosten $\Theta(n^2)$ erhalten.


### Splay-Bäume
#### Intuition

Es ist nicht leicht zu sehen, wie wir das Move-to-Root-Verfahren anpassen können, damit wir eine bessere Selbstanordnung bekommen. 1985 haben Sleator und Tarjan genau das geschafft. Eine kleine Variation von Move-to-Root funktioniert erstaunlich gut.

Intuitiv liegt das Problem von Move-to-Root darin, dass beim Hochziehen von `x` die benachbarten Knoten (z.B. das `y` im Beispiel oben) nicht mit zur Wurzel hochgezogen werden. Der Trick ist simpel: Statt zuerst um `y` und dann um `z` zu rotieren machen wir es in umgekehrter Reihenfolge. Warum das funktioniert ist alles andere als offensichtlich.

#### Rotationen

Wir unterscheiden drei Fälle:
- **Zig**: Liegt `x` unmittelbar unter der Wurzel, so rotieren wir `x` nach oben (wie gewohnt).


- **Zig-Zag**: Ist `y` das linke Kind von `z` und `x` das rechte Kind von `y` so rotieren wir zuerst um `y` und erst dann um `z` (wie gewohnt).


- **Zig-Zig**: Sind `x` und `y` je das linke Kind ihrer Väter, so rotieren wir zuerst um `z` und erst dann um `y` (**neu!**).


Die verbleibenden Fälle *Zag*, *Zag-Zig* und *Zag-Zag* sind einfach spiegelverkehrt.

Der verblüffende Trick ist also lediglich das Zig-Zig, der Rest ist wie bei Move-to-Root. Intuitiv zieht die Zig-Zig Operation die Nachbarschaft von `x` (den Knoten `y` im Beispiel) mehr mit nach oben, im Gegensatz zu den Move-to-Root Operationen.

Diese neue Datenstruktur heisst *Splay-Baum* (oder Splay Tree) und das Hochrotieren nach dieser Methode *splayen*^[Leider gibt es keine schönen deutschen Begriffe dafür].

#### Analyse

Nun sollten wir uns vergewissern, dass dieses *splayen* auch effektiv funktioniert. Wir führen eine amortisierte Analyse durch. Wir erinnern uns an die Zutaten einer amortisierten Analyse mit einem Kontostand (Potentialfunktion):
$$\underbrace{a_l}_{\text{amortisierte Kosten}} = \underbrace{t_l}_{\text{tatsächliche Kosten}} + \underbrace{bal_l - bal_{l-1}}_{\text{Kontostandsdifferenz}}.$$

In unserer Situation ist das nicht ganz einfach und wir müssen uns einen cleveren Kontostand ausdenken. Bei unseren bisherigen Überlegungen war der Kontostand zu Beginn jeweils gleich Null. Dann genügte es zu zeigen, dass wir nie ins Minus gehen, um zu argumentieren, dass die tatsächlichen Kosten die amortisierten Kosten nicht überschreiten.

Jetzt wollen wir das verallgemeinern: Wir sagen, dass wir mit irgendeiner Baumstruktur beginnen, welcher wir auch schon einen Kontostand zuordnen. Vom imaginären Konto dieses Initialbaumes dürfen wir dann auch abheben aber müssen dann am Ende vorsichtig vergleichen mit der Strukturänderung, die wir durchführen.

Wie definieren wir den Kontostand? Wir wählen ein Gewicht $w(i)$ für jeden Knoten $v$ mit Schlüssel $i$ im Splay-Baum. Wir definieren $s(v) = \sum_{i \text{ im Teilbaum von } v} w(i)$ als die *Grösse* des Knotens $v$ und $r(v) = \log (s(v))$ als Rang von $v$. Die genauen Gewichte wählen wir erst später. Wären alle Gewichte gleich $1$, dann wären $s(v)$ die Teilbaumgrössen und $r(v)$ die Höhe des Teilbaumes bei perfekter Balanciertheit. Das Gewicht gehört also zum Schlüssel, die Grösse und der Rang aber zum Knoten.

Als Kontostand wählen wir $bal := \sum_{v \in Baum} r(v)$, die Summe aller Ränge.

Die tatsächlichen Kosten wählen wir als $t_l = max \{ \text{Anzahl Rotationen},1 \}$, da wir auch konstante Kosten haben, falls wir nichts rotieren müssen.

Jetzt schauen wir wie die Operationen den Kontostand verändern,

- **Rotation 0:** Gesucht ist der Schlüssel an der Wurzel
Die tatsächlichen Kosten sind $1$ und es wird keine Rotation durchgeführt. Somit bleibt der Kontostand unverändert und $a_l = 1$.

- **Rotation 1:** Zig
Die Grössen und damit auch die Ränge von `v` und `w` ändern sich bei der Rotation. Für alle anderen Knoten im Baum ändert sich aber nicht.
$$bal_l-bal_{l-1} = r'(v) - r(v) + r'(w) - r(w)$$
Wir sehen, dass $r'(v) > r(v)$ und $r'(w) < r(w)$ gilt und daraus folgt, dass $r'(w) - r(w) < 0$ und $bal_l - bal_{l-1} < r'(v)-r(v)$ gilt. Mit den konstanten tatsächlichen Kosten $t_l = 1$ ergibt sich damit
$$\text{(zig) } a_l \leq (r'(v) - r(v)) + 1.$$

- **Rotation 2:** Zig-Zag
Das kann man nun im gleichen Stil, aber mit etwas mehr Rechenaufwand, für die Zig-Zag und die Zag-Zig Operationen machen. Dabei sieht man, dass gilt:

$$\text{(zigzag) } a_l \leq 3(r'(v)-r(v)).$$

- **Rotation 3:** Zig-Zig
Die selbige Schranke erhält man auch für die Zig-Zig und Zag-Zag Operationen.
$$\text{(zigzig) } a_l \leq 3(r'(v)-r(v)).$$

Ein Zugriff auf ein Element führt aber mehrere Operationen aus. Wie ändert sich der Kontostand über all diese Hochrotationen hinweg?
Für eine zweiten Operation ergibt sich sowas wie: $a_l \leq 3(r'(v)-r(v)) + 3(r''(v)-r'(v))$ Dabei kürzt sich der Zwischenschritt heraus und es bleibt nur der Rang zu Beginn und am Ende $a_l \leq 3(r''(v)-r(v))$. Das selbe gilt für den ganzen Weg bis zur Wurzel:

**Zugriffslemma:** Die amortisierte Kosten fürs Splayen am Knoten $v$ zur Wurzel $z$ kann man abschätzen mit $a_l\leq 3(r(z) - r(v)) + 1$.

Jetzt müssen wir noch die Gewichte definieren und erklären wie sich der Kontostand verändert. Wir betrachten $m$ Suchoperationen auf $n$ Schlüsseln.

Als Gewicht wählen wir $w(i)= \frac{1}{n}$ für alle $i$, sodass $W = \sum w(i) = 1$.

Setzen wir ins Zugriffslemma ein: $a_l \leq 3 \cdot (\log 1 - \log(r(v)) +1 \leq 3(0 - log(\frac{1}{n}) + 1 = 3 \cdot log (n) + 1$

Daher können wir nun sagen, dass das Hochsplayen amortisiert nur $3 \log n + 1$ kostet, phänomenal! Was nun noch fehlt ist die Kontostandsanalyse: Sind wir sicher, dass wir nicht einfach das Konto überstrapaziert haben? Wie unterscheidet sich der Anfangskontostand $bal_0$ vom Endkontostand $bal_m$?

Pro Knoten $v$ kann die Grösse $s(v)$ von $1$ auf $\frac{1}{n}$ zurückgehen. Sein Rang ändert sich damit maximal um $\log 1 - \log \frac{1}{n}$. Das ist natürlich grosszügig geschätzt, denn es kann nicht für *jeden* Knoten von $1$ auf $\frac{1}{n}$ zurückgehen.

Für die Gesamtdifferenz gilt also $bal_0 - bal_m \leq n \cdot(0-\log \frac{1}{n}) = n \log n$.

Die Gesamtkosten sind also in $\O(m \cdot log (n) + n \cdot log (n) + m)$.

Wir haben hiermit gezeigt, dass sich Splay-Bäume asymptotisch genauso verhalten wir AVL-Bäume. Warum das so ist, versteht niemand so genau. Die Intuition warum Zig-Zig besser funktioniert als Move-to-Root haben wir oben gegeben und dass es rechnerisch aufgeht, haben wie soeben gezeigt.

Was man auch zeigen kann: Splay-Bäume sind *häufigkeitsoptimal*. Wir haben also *statische Optimalität*, was bedeutet, dass ein Splay-Baum höchstens einen konstanten Faktor langsamer ist, als der häufigkeitsoptimale Suchbaum, den wir gestern mit dynamischer Programmierung aufwändig generiert haben.

Das ist das Faszinierende an Splay-Bäumen: Er ist von alleine gleich gut wie ein AVL-Baum, ohne bewusst zu balancieren, *und* gleichzeitig auch so gut wie der optimale statische Suchbaum.

Wir würden gerne auch sagen: Splay-Bäume sind auch dynamisch optimal, also auch gegen einen dynamisch angepassten Suchbaum höchstens um einen konstanten Faktor schlechter. Das wäre dann eine sehr starke Aussage, genauso wie wir es bei Move-To-Front gezeigt hatten. Man vermutet, dass der Splay-Baum diese Eigenschaft hat und in der Praxis beobachtet man sie auch häufig, aber ob dem wirklich so ist, ist bis heute offen und ein Forschungsthema bekannt als *Dynamic-Optimality-Conjecture*.

Jetzt fragen wir uns noch ob Splay-Bäume auch gute Wörterbücher sind? Wie implementieren wir also die drei Operationen?

- **Suche nach $k$**
Wir suchen wie in jedem anderen Suchbaum auch. Endet die Suche erfolgreich im Knoten $v$, so splayen wir $v$ hoch. Enden wir erfolglos in einem Blatt, so splayen wir dessen Vater $p$ an die Wurzel.


- **Einfügen von $k$**
Wenn $k$ nicht im Baum erhalten ist, landen wir in einem Blatt. In diesem Fall splayen wir den Vater `k'` des Blattes an die Wurzel. Wir knipsen den linken Teilbaum dieser neuen Wurzel `k'` ab und fügen `k` als neue Wurzel ein.


- **Entfernen von $k$**
Wir splayen $k$ zuerst an die Wurzel und werfen den Knoten weg. Entstehen dabei zwei Teilbäume $A$ und $B$, so splayen wir das grösste Element aus $A$ (den symmetrischen Vorgänger $k''$ von $k$). Dieser Vorgänger $k''$ hat kein rechtes Kind, weshalb wir dort $B$ anhängen können.


Für diese Operationen gibt es keine formale amortisierten Analysen aber man beobachtet einfach, dass sie in der Praxis gut funktionieren.

#### Zusammenfassung
Für die meisten Anwendungen sind Splay-Bäume unglaublich gut. Es gibt aber schon auch Nachteile, z.B. sind die Operationen nur amortisiert schnell^[Also ist nicht zwingend jede einzelne Operation in $\O(\log n)$.] und ein Splay-Baum lässt sich deutlich schlechter parallelisieren als ein AVL-Baum, da wir bei jeder Operation den ganzen Baum sperren müssen. Durch die einfache Implementierung und die Kombination von logarithmischer Laufzeit und statischer Optimalität überwiegen in der Praxis aber oft die Vorteile.