# 8 Suchbä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).

## Natürliche Suchbäume
### Suchen
Gestern haben wir gesehen, was ein *binärer Suchbaum* ist. Wir haben einen binären Baum mit folgender Eigenschaft: Für alle Knoten gilt, dass die Schlüssel im linken Teilbaum kleiner sind als der Schlüssel im Knoten und der Schlüssel im Knoten ist kleiner als alle Schlüssel im rechten Teilbaum.


Suche (ab Knoten p nach Schlüssel k)
	if p null then erfolglos
	else if k < key von p then suche(links von p, k)
	else if k > key von p then suche(rechts von p, k)
	else gefunden

Unser Wunsch an die Laufzeit für diesen Suchbaum war $\O(\log n)$. Das können wir auch erreichen, wenn wir den Baum statisch aufbauen können, sich die Schlüsselmenge also nicht dynamisch ändert. Wir bauen den Baum balanciert (so wie beim Heap für Heapsort) und erreichen so logarithmische Höhe.

Wir wollen das jetzt dynamisch machen, also auch Einfüge- und Löschoperationen unterstützen. Die natürlichste Art die Einfügeoperation zu unterstützen ist die folgende:

### Einfügen

Einfügen(k)
	Suche ab der Wurzel nach k
	Finden wir k im Baum, müssen wir nichts einfügen
	Sonst, landen wir in einem Blatt p
	Ersetze das Blatt durch einen neuen Knoten mit dem Schlüssel k, 

Erreichen wir damit logarithmische Laufzeit? Im schlechtesten Fall leider nicht. Wenn wir in einen leeren Baum die Schlüssel $1,2,\dots,n$ der Reihe noch einfügen, dann degeneriert der Suchbaum zu einer linearen Liste mit linearer Tiefe. Also: Worst Case $\Theta(n)$.

Ist es wenigstens im Mittel gut? (gemittelt über alle möglichen Einfügereihenfolgen). Wie beim Quicksort, können wir argumentieren, dass der *durchschnittliche* Schlüssel ein guter Pivot, respektive eine gute Wurzel ist. Mit der selben Analyse erhalten wir eine mittlere Suchbaumhöhe von $\Theta(\log n)$.

### Entfernen
Wie können wir Schlüssel entfernen?
Es genügt nicht, den entsprechenden Knoten zu finden und zu löschen, da wir dabei auch alle Schlüssel in seinen Teilbäumen verlieren. Zusätzlich müssen wir vorsichtig sein, dass wir die Suchbaumeigenschaft nicht zerstören.

Wir unterscheiden drei Fälle:


Entfernen(k)
	Suche ab der Wurzel nach k
	Endet mit Knoten p mit key(p) = k
	1. Fall: p hat kein Kind -> Knoten einfach löschen
	2. Fall: p hat ein Kind -> lenke Zeiger vom Vater aufs Kind
	3. Fall: p hat zwei Kinder -> der interessante Fall!

Der spannende Fall ist also, wenn der zu löschende Knoten zwei Kinder hat. Wir können ihn dann nicht einfach löschen, da es danach keine einfache Möglichkeit gibt, die beiden darunterliegenden Teilbäume in der verbleibenden Suchbaum einzubetten. Der Trick ist es nun stattdessen ein anderes Element zu löschen, welches nur höchstens ein Kind hat.

Für dieses andere Element interessieren wir uns nun für den Knoten mit dem grössten Schlüssel im linken Teilbaum von $p$. Dies ist der nächstkleinere Wert vor $k$ in der sortierten Folge aller Schlüssel, genannt (symmetrischer) Vorgänger. Das selbe gilt für den kleinsten Schlüssel im rechten Teilbaum, genannt (symmetrischer) Nachfolger.

Warum können wir sicher sein, dass die nächstkleineren und grösseren Schlüssel in der global sortierten Folge wirklich immer im Teilbaum von $p$ liegen? Die sortierte Reihenfolge entspricht der Inorder-Traversierung des Suchbaumes. Da beide Kinderteilbäume von $p$ nicht leer sind, stammen also die Schlüssel unmittelbar vor und nach $k$ in der sortierten Folge aus dem Teilbaum von $p$.

Was bringen uns diese Vorgänger und Nachfolger? Der Vorgänger und Nachfolger haben je höchstens ein Kind. Denn hätten sie zwei Kinder, so wären sie in der Traversierung nicht direkt vor/nach $k$. Somit ist das Entfernen dieser Knoten einer der beiden trivialen Fälle.

Entfernen im dritten Fall bei Knoten k:
	Finde den sym. Vorgänger; 
	> gehe 1 Schritt links, 
	> gehe solange rechts wir moeglich (so erreicht man den sym. Vorgänger)
	Tausche k mit sym. Vorgänger 
	Knipse sym. Vorgänger ab oder leite von Vater um. (1. oder 2. Fall)


In der Praxis gibt es viele Tricks um den Code zu vereinfachen. Ein cooler Trick ist es statt Blätter mit null Zeigern ins Leere zeigen zu lassen, allozieren wir einen zusätzlichen Knoten auf den alle Blätter zeigen. Bevor wir dann jeweils eine Suche starten, schreiben wir diesen Schlüssel auf diesen zusätzlichen Knoten. Damit wissen wir, dass die Suche immer den Schlüssel finden wird.

Jetzt haben wir also eine Laufzeit von $\O(\text{Höhe})$ erreicht für alle Operationen, falls unser Baum am Anfang leer war! Wie hoch wird dieser Baum?
Worst Case: $\Theta(n)$
Best Case: $\Theta(\log n)$

Und im Durchschnitt? Was heisst denn überhaupt im Durchschnitt bei so vielen verschiedenen Operationsmöglichkeiten? Wie schon oben beim Einfügen erwähnt, wenn wir wie bei Quicksort annehmen, dass wir eine zufällige Reihenfolge als Eingabe bekommen, also jede Permutation der Eingabe gleichwahrscheinlich ist, dann erhalten wir Mittel auch $\Theta(\log n)$. Die Analogie zu Quicksort ist wirklich sehr gross: Wenn wir die Schlüssel einer Folge der Reihe nach in einen natürlichen Suchbaum einfügen, ergibt sich exakt die selbe Baumstruktur, wie bei Quicksort auf der selben Folge, wenn jeweils das erste Element als Pivot gewählt wird.

Was passiert, wenn wir statt über die Reihenfolge über die Gestalt des Baumes mitteln? Eine solche *Gestaltsanalyse* ergibt nicht genau das gleiche, denn zum Beispiel für drei Schlüssel gibt es sechs Permutationen aber nur fünf Suchbaumgestalten (da 2 1 3 und 2 3 1 den selben Baum ergeben). Wenn man es genau ausrechnet kommt man auf $\Theta(\sqrt{n})$.

Im Schnitt funktionieren natürliche Suchbäume also ganz gut, aber wie immer hätten wir gerne Worst Case Garantien.

## AVL-Bäume

### Motivation
Wir sind auf der Suche nach einer Bedingung, die uns logarithmische Laufzeit garantiert.

Ganz simple Bedingung: logarithmische Höhe und immer die folgende Gestalt erhalten: (im letzten Level alles von links her aufgefüllt, wie beim Heap)

/\
/ \
/ \
/ ---
/___|

Änderungsoperationen müssen diese Bedingungen erhalten. Können wir in logarithmischer Zeit diese Bedingung wiederherstellen? Wenn wir eine neues Blatt irgendwo unten einfügen müssen wir unter Umständen linear viele Schlüssel verschieben, um die Form-Bedingung zu erhalten. Unsere Bedingung ist viel zu stark, um sie einfach einhalten zu können. Wir suchen also nach etwas, das uns eine leicht schwächere Höhenbedingung gibt, dafür aber sehr einfach einzuhalten bleibt.

### AVL-Baum-Bedingung
Sowas gibt es und ist ein wahres Kunststück der Ingenieurwissenschaften.

Die beiden sowjetischen Mathematiker Adelson-Velskii und Landis hatten schon 1962 eine gute Idee für eine Bedingung, die einhaltbar ist und doch gute Laufzeiten garantiert. Für jeden Knoten muss gelten, dass sich die Höhe des linken und des rechten Teilbaumes um höchstens 1 unterscheiden (AVL-Bedingung).


Was sagt diese AVL-Bedingung über die Höhe? Die Suche geht natürlich in $\O(\text{Höhe})$. Bevor wir uns überlegen, wie wir diese AVL-Bedingung bei den Operationen einhalten können, denken wir darüber nach, ob wir überhaupt eine logarithmische Höhe garantieren können?

Dazu können wir uns auch fragen: Wie viele Blätter hat ein AVL-Baum der Höhe $h$ mindestens? Dies ist etwas einfacher, als die Anzahl Schlüssel zu zählen. Und da jeder Baum hat immer genau ein Blatt mehr hat als innere Knoten (wo die Schlüssel stehen) kommt es fast aufs Gleiche reaus. Sei dazu $mb(h)$ die Mindestblattzahl eines AVL-Baumes der Höhe $h$.


Um möglichst kleine Bäume zu bauen, nutzen wir das erlaubte Ungleichgewicht immer voll aus, also verknüpfen immer $mb(h) = mb(h-1) + mb(h-2)$. Für kleine Höhen gibt das:

| $h$ | 0 | 1 | 2 | 3 |
|---------|---|---|---|---|
| $mb(h)$ | 1 | 2 | 3 | 5 |

Das sind die Fibonacci-Zahlen (leicht verschoben)

$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, ...$
$F_j = F_{j-1} + F_{j-2}$
$F_i = 0.7 \cdot 1.6^i$
$mb(h) = F_{h+2} \approx 0,7 \cdot 1.6^{h+2}$

Die Anzahl Blätter wachst also exponentiell. Für eine fixe Anzahl Blätter können wir garantieren, dass die Höhe beschränkt ist durch $h \leq 1.44 \log n$.

Durch diese Auflockerung der Balancierbedingung verlieren wir also höchstens 40 Prozent im Vergleich zum perfekt balancierten Baum, den wir dynamisch nur sehr schwer erhalten können.

### Einfüge-Operation

Jetzt wo wir wissen, dass ein AVL-Baum nie zu hoch wird, wollen wir uns überlegen, wie wir bei den Operationen die Bedingung erhalten können. Starten wir mit dem Einfügen.

Versuchen wir es möglichst ähnlich wie im natürlichen Suchbaum zu machen. Suchen wir also das Blatt, bei dem der neue Schlüssel hingehört, und setzen dort den neuen Knoten ein.

Jetzt können wir potentiell bei einigen Knoten die AVL-Bedingung verletzt haben. Wo kann das passiert sein? Das neue Blatt liegt nur in den Teilbäumen der Knoten, welche auf dem Suchpfad des Schlüssels liegen. Also kann die AVL-Bedingung auch nur an solchen Knoten verletzt sein. Sie kann auch nur verletzt sein, wenn sich die Höhe eines Teilbaumes effektiv geändert hat. Wir können also vom neu eingefügten Blatt her nach oben aufsteigen und jeweils prüfen ob sich was geändert hat und ob wir die AVL-Bedingung verletzen.

Als Information brauchen wir dazu in jedem Knoten die Höhe der beiden Teilbäume. Diese Höhen können aber für grosse Bäume auch gross werden und genau genommen sind wir ja nur daran interessiert, ob die Teilbäume gleich hoch sind, ober welcher der beiden Bäume um eines höher ist. Alles was wir also speichern pro Knoten ist $-1$, $0$ oder $1$, was uns die Balance angibt.

#### Fallunterscheidung nach dem Vater von k
Jetzt unterscheiden wir einige Fälle:

**Fall I)** $k$ wurde links von $p$ eingesetzt (Fall II) für $k$ rechts von $p$ geht analog)


Wir unterscheiden, was die Balance $bal(p)$ vor dem Einfügen war:

**Fall i)** $bal(p) = -1$: Das ist unmöglich, weil $p$ ja vorher noch gar keinen linken Teilbaum hatte

**Fall ii)** $bal(p) = 1$: Dann ist $p$ jetzt balanciert, da beide Teilbäume jetzt gleich hoch sind. Die Höhe des Teilbaumes in $p$ hat sich nicht geändert, also hat sich für die Vorgänger von $p$ die Balance sicher auch nicht geändert. Wir updaten also nur $bal(p) = 0$ und sind fertig.

**Fall iii)** $bal(p) = 0$: Dann ist neu $bal(p) = -1$. Und jetzt hat sich die Höhe des Teilbaumes von $p$ um eines vergrössert, sodass wir auch die Vorgänger von $p$ behandeln müssen. Wir behandeln dies mit einer Funktion ``upin(p)``, welche aufsteigt und diese Änderung dort behandelt.

#### Implementierung von ``upin(p)``

Diese ``upin`` Funktion hat als Invariante:
- Die Höhe im Teilbaum von $p$ ist um $1$ gewachsen.
- $bal(p) \neq 0$.

Es gibt wieder zwei symmetrische Fälle:

**Fall I)** $p$ ist das linke Kind seines Vorgängers $q$
(Der Fall II) mit $p$ als rechtem Kind ist wieder analog.)


Nun unterscheiden wir lokal wir nach der Balance des Vaters, nenne wir ihn $q$.

**Fall i)** $bal(q) = 1$: Wenn die Balance von $q$ vorher $1$ war, dann war der rechte Teilbaum von $q$ um eins höher als der linke. Wenn nun also der linke Teilbaum um eins gewachsen ist, so ändert sich die $bal(q) = 0$, aber die Höhe des Teilbaumes hat sich nicht geändert und wir sind fertig.

**Fall ii)** $bal(q) = 0$: Dann ist das Gleichgewicht jetzt verletzt, weshalb wir $bal(q) = -1$ setzen und mit ``upin(q)`` fortfahren müssen.

**Fall iii)** $bal(q) = -1$: Der dritte Fall ist jetzt der heikle. Jetzt haben wir den Teilbaum erhöht, der sowieso schon höher war.

Nehmen wir an, das neue Blatt sei im linken Teilbaum von $p$, also so:


Können wir diese Teilbäume so umgruppieren, dass die Suchbaumeigenschaft erhalten bleibt, aber die AVL-Bedingung wieder hergestellt wird und wir nicht viel ändern müssen?

Ja, das geht! Mit folgenden Zeigeränderungen:


Wir nehmen den Baum quasi auseinander und setzen ihn mit $p$ als neuer Wurzel wieder zusammen und achten dabei darauf, dass die drei Teilbäume am richtigen Ort landen. Eine solche Strukturänderung nennt man Rotation, hier konkret eine *Rechtsrotation*, und wir können sie in wenigen Zeigeränderungen durchführen.

Danach ist $bal(p) = 0$ und $bal(q) = 0$. Da nun alles balanciert und die Teilbaumhöhe unverändert ist, sind wir fertig. Das war aber etwas glücklich, denn das hat nur geklappt, weil das neue Element im linken Teilbaum von $p$ war.

Im anderen Fall, liegt das neue Blatt im rechten Teilbaum von $p$, also so: $bal(p) = 1$ und $bal(q) = -1$.


Hier nützt eine solche Rechtsrotation nichts, da wir das Problem einfach auf die rechte Seite verlagern würden. Da müssen wir genauer hinschauen und den Teilbaum mit dem neuen Element etwas genauer auseinandernehmen.


Wir rotieren so rum, dass $r$ die neue Wurzel wird:


Danach sind die neuen Balancen $bal(p) = 0$, $bal(r) = 0$, $bal(q) = 1$. Der Teilbaum unter $r$ ist also balanciert und gleich hoch wie vor der Doppelrotation. Daher können wir aufhören und müssen ``upin()`` nicht weiter aufrufen. Im Fall, wo das neue Element an $C$ hängt, ist $bal(p) = -1$, $bal(r) = 0$, $bal(q) = 0$ und wir können auch aufhören.

Da wir dieses Ändern der Zeiger mittels zweier Rotationen implementieren können, nennt man diese Operation *Doppelrotation*.

Wir beobachten, dass wir beim Einfügen mit ``upin`` nach einer einzigen Rotation jeweils aufhören können. Die Strukturänderung beim Einfügen ist also in $\O(1)$.

**Fragen für nächste Woche:**
- Ist diese Investition in die Strukturänderung für längere Zeit gut, oder müssen wir immer wieder rotieren?
- Muss ``upin`` beim wiederholten Einfügen immer wieder weit dem Pfad entlang hochlaufen oder kann das nur ab und zu passieren?