Binäre Suchbäume
"eins links, eins rechts"
Autor(en): Andreas Frommer, Sarah Zigman - April 2004
Kapitelübersicht
Ein einführendes Glücksspiel, welches auf das Prinzip der binären Suche führt.
Es werden Binärbäume als Graphen eingeführt. Dann werden binäre Suchbäume mit ihren Operationen 'Suchen', 'Einfügen' und 'Löschen' behandelt.
Wir behandeln, wie durch Rotationen in AVL-Bäumen die Höhe klein gehalten wird und sehen die Konsequenzen für 'Suchen', 'Einfügen' und 'Löschen'.
Heaps sind besondere Binärbäume mit gegenüber Suchbäumen eingeschränkter Funktionalität. Wir behandeln die Operationen 'Einfügen' und 'Maximum Entfernen'.
Arbeitsblatt
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 
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
herzustellen und zu begründen.
Drucken
Inhalt
Viele Aufgaben in der Datenverarbeitung kann man charakterisieren durch:
Suche nach einem Datensatz mit einem bestimmten Schlüssel
Damit die Suche bei großen Datenmengen nicht zu lange dauert, gibt es verschiedene Datenstrukturen, in denen die Informationen abgelegt werden:
(einfache) Binäre Suchbäume, AVL-Bäume und Heaps
Deren Funktionsweise wird in zahlreichen Applets interaktiv erfahrbar gemacht.
Glossar
