Einführung Informatik/Algorithmen und Datenstrukturen
Prof. Dr. Reiner Dumke                                                                                                                    SoSe 01

Dr. Martin Endig, Ilona Blümel, Dr. Martina Engelke, Bert Freudenberg, Dr. Reinhard Köppe, Dr. Fritz Zbrog

19. Übungsblatt

Aufgabe 72
Erweitern Sie die Klasse LinkedBinaryTree um weitere Methoden für binäre Suchbäume:
a) für die Bestimmung der Anzahl der Knoten,
b) zur Bestimmung der Höhe des Baumes und
c) zur Überprüfung der Ausgeglichenheit.

Aufgabe 73
Erläutern Sie den in der Vorlesung vorgestellten Algorithmus für das Löschen von Knoten im
Suchbaum am Beispiel des Suchbaumes aus Aufgabe 70. Die Knoten sollen in folgender
Reihenfolge gelöscht werden: 7, 3, 5, 4, 8, 2.
Aufgabe 74
Schreiben Sie eine Methode delete(Comparable x) für das Löschen von Knoten mit gegebenem
Element in Suchbäumen (keine AVL-Bäume!). Welche Fälle sind zu unterscheiden?
Aufgabe 75
a) Was ist ein ausgeglichener (AVL-) Baum? Weshalb ist es erforderlich, binäre Bäume
auszugleichen?
b) Erläutern Sie den Algorithmus für das Einfügen von Knoten mit gegebenem Element in
AVL-Bäumen am Beispiel des Einfügens der natürlichen Zahlen von 14, 15, 17, 7, 5, 10 und
16 in dieser Reihenfolge.
c) Ist es sinnvoll, die bisher genutzte Datenstruktur Baum zu erweitern?
Aufgabe 76
Gegeben sei folgender AVL-Baum:

Löschen Sie die Knoten 15, 38, 26, 25 und 12 in dieser Reihenfolge. Geben Sie alle notwendigen
Schritte (Rotationen) beim Löschen an, damit der Baum ausgeglichen bleibt. Skizzieren Sie den
AVL-Baum nach jedem Löschen eines Elementes.