MathePrisma

Arbeitsblatt: Binäre Suchbäume

Aufgabe 1

Führe die folgenden Operationen einmal für einen gewöhnlichen binären Suchbaum und einmal für einen AVL-Baum aus. Skizziere beide Bäume nach der letzten Operation.

füge die Schlüssel 20, 4, 10, 5, 8 und 6 (in dieser Reihenfolge) ein.
lösche 6
lösche 20
füge 6 ein
füge 20 ein

Aufgabe 2

Skizziere alle möglichen AVL-Bäume der Höhen 1, 2, 3 und 4. (Dabei spielt nur die Struktur der Bäume eine Rolle, nicht die Werte der Schlüssel.)

Aufgabe 3

Formuliere einen Algorithmus, der unter Verwendung der Balance-Indizes die Höhe eines AVL-Baumes bestimmt. Der Algorithmus soll in der Wurzel starten und dann nach unten weiter laufen.
Kann man auf ähnliche Weise im AVL-Baum auch das Blatt mit der geringsten Tiefe finden?

Aufgabe 4

Beschreibe in Worten, wie eine Rechtsrotation um den Knoten w abläuft. Verwende dabei Formulierungen wie 'der linke Teilbaum von w wird linker Teilbaum des Vaters von w' usw.

Aufgabe 5

Überlege, wie man einen Heap dazu verwenden kann, eine Folge von Zahlen $a_1, a_2,..., a_n$ nach absteigender Größe zu sortieren.

Aufgabe 6*

Professor Sloppy meint: statt im binären Suchbaum beim Löschen den Knoten durch das Minimum im rechten Teilbaum zu ersetzen, kann ich ihn genauso gut durch das Maximum im linken Teilbaum ersetzen.
Hat der Professor recht?

Aufgabe 7*

Versuche, ausgehend von Aufgabe 2 einen Zusammenhang zwischen der Mindestknotenzahl m(h) eines AVL-Baumes der Höhe h und den Fibonacci-Zahlen

$f_{-1}=1, f_0 = 1, f_1 = 2, f_{n} = f_{n-1} + f_{n-2}, \; n \geq 2$

herzustellen und zu begründen.