Binäre Suchbäume | MathePrisma

neu: löschen

Die Operation löschen( s ) ist etwas komplexer, je nachdem, wo sich der zu löschende Schlüssel befindet.

Lösche Wurzel, innere Knoten und Blätter!

Gib in dem Textfeld unten an, welcher Knoten des Suchbaumes gelöscht werden soll und beobachte jeweils den Löschvorgang.

Hast du den Löschvorgang durchschaut? Dann beantworte die folgenden Fragen.

Markiere durch Anklicken die richtigen Aussagen.

Der zu löschende Knoten muss zunächst gesucht (und gefunden) werden.
Die Wurzel kann immer ohne weitere `Maßnahmen' einfach entfernt werden.
Die Wurzel kann manchmal ohne weitere `Maßnahmen' einfach entfernt werden.
Innere Knoten hinterlassen beim Entfernen eine bleibende Lücke.
Nach dem Löschen eines Blattes sind keine weiteren Schritte nötig.
Das Löschen eines Knotens mit zwei Teilbäumen ist am spannendsten

Der folgenden Lösch-Algorithmus berücksichtigt alle möglichen Fälle.

löschen

Algorithmus zum Löschen von Schlüssel s

Suche im Baum nach einem Knoten mit Schlüssel s.
Ist kein solcher Knoten vorhanden, so bist du fertig.

Andernfalls:

Ist der gefundene Knoten ein Blatt, so entferne das Blatt.
Besitzt der gefundene Knoten nur einen Sohn, so ersetze den Knoten durch diesen Sohn (gesamten Teilbaum 'umhängen').
Besitzt der gefundene Knoten zwei Söhne, so ersetze den Knoten durch das Minimum des rechten Teilbaumes. (Bemerkung: Für dieses Minimum ist ein eigenständiger Löschvorgang durchzuführen. Dieser ist `einfach', denn das Minimum hat keinen linken Sohn.)

Über das Löschen kannst du mit dem folgenden Puzzle noch einmal nachdenken

weil's so wichtig ist

Noch eine letzte Testfrage zum Löschen:

Die Lücke, die beim Löschen eines inneren Knotens entsteht, wird bei zwei Söhnen...

... immer durch den rechten Sohn ersetzt.
... manchmal durch den rechten Sohn ersetzt.
... immer durch den linken Sohn ersetzt.
... manchmal durch den linken Sohn ersetzt.
... immer durch das Minimum des linken Teilbaumes ersetzt.
... immer durch das Maximum des linken Teilbaumes ersetzt.
... immer durch das Minimum des rechten Teilbaumes ersetzt.
... immer durch das Maximum des rechten Teilbaumes ersetzt.

In dem folgenden Experiment hast du Gelegenheit, mit allen drei Operationen gleichzeitig zu arbeiten.

volles Programm

Hier kannst du mit binären Suchbäumen arbeiten.
Der gerade zugängliche Datensatz ist farblich hervorgehoben.

sehr wichtig!

Wie groß ist eigentlich der Aufwand der einzelnen Operationen?

Aufwand

Fazit

Hohe Suchbäume sind unerwünscht, denn das Suchen nach Knoten in großer Tiefe wird dann relativ aufwendig. Dasselbe gilt für Löschen und Einfügen.
Erstrebenswert sind daher möglichst niedrige Suchbäume! Hierzu lernen wir im nächsten Abschnitt eine raffinierte Technik kennen.