19.6 Das Löschen von Elementen

Allgemeines

Jetzt kommt die schwierigste Methode von allen, das Löschen von Knoten des Baumes. Aber wir werden jetzt ganz systematisch vorgehen und dadurch auch dieses komplizierte Problem in den Griff bekommen.

Zunächst einmal überlegen wir uns den groben Algorithmus. Das Löschen besteht aus zwei Schritten: im Schritt 1 muss der zu löschende Knoten gefunden werden, und im Schritt 2 wird der Knoten dann gelöscht.

Suchen des zu löschenden Elementes

Das Suchen des Elementes ist einfach und kann grob ungefähr so formuliert werden:

Löschen eines Elementes

Dabei ist del der Wert des zu löschenden Elementes und root der Wert der Wurzel. Man erkennt leicht, dass es sich hierbei um einen rekursiven Algorithmus handelt.

Löschen des gefundenen Elementes

Wir unterscheiden hier drei Fälle.

Fall 1: Der zu löschende Knoten ist ein Blatt, hat also weder einen linken noch einen rechten Nachfolger.

Fall 2: Der zu löschende Knoten ist ein innerer Knoten mit nur einem Nachfolger.

Fall 3: Der zu löschende Knoten hat zwei Nachfolger.

Schauen wir uns die drei Fälle jetzt etwas näher an.

Fall 1: Löschen eines Blattes

Hier muss der Zeiger des Vorgängerknotens, der auf das zu löschende Blatt zeigt, auf null gesetzt werden. Weitere Einzelheiten...

Fall 2: Löschen eines Knotens mit genau einem Nachfolger

Hier muss der left- bzw. der right-Zeiger des Vorgängerknotens auf den Nachfolger des zu löschenden Knotens gesetzt werden. Weitere Einzelheiten...

Fall 3: Löschen eines Knotens mit genau zwei Nachfolgern

Hier ist das Löschen zunächst nicht so einfach. Aber man kommt recht schnell auf eine leicht zu merkende Faustregel: Ersetze den Inhalt des zu löschenden Knotens durch den größten Wert des linken Teilbaums oder alternativ durch den kleinsten Wert des rechten Teilbaumes. Lösche anschließend den entsprechenden Knoten mit der bei Fall 1 bzw. Fall 2 beschriebenen Methode. Weitere Einzelheiten...
  1. Binärbäume - Allgemeines
  2. Binäre Suchbäume
  3. Das Einfügen von Elementen
  4. Das Anzeigen von Elementen
  5. Das rekursive Einfügen von Elementen
  6. Das Löschen von Elementen
  7. Implementierung mit Hilfe von Arrays
  8. AVL-Bäume
  9. B-Bäume

Diese Webseite über Bäume wird nicht weiter entwickelt. Statt dessen können Sie die Buchversion des Skriptes gegen gleichwertiges Tauschmaterial oder einen kleinen Unkostenbeitrag Ivon mir erhalten.

Den ersten Teil der Folge 19 können Sie hier kostenlos als PDF-Datei herunterladen.

Schreiben Sie mir eine E-Mail, wenn Sie Interesse haben.

Abiturienten NRW

Gehen Sie bitte auch auf die "offizielle" BinTree-Seite!

Der rekursive Lösch-Algorithmus

Ich kann Ihnen hier ein altes Pascal-Beispiel eines solchen Löschalgorithmus anbieten. Es ist nicht Ziel dieses BlueJ-Lehrgangs, das Löschen in einem BlueJ-Projekt zu implementieren; auch die Richtlinien des Landes NRW sehen nur vor, dass die Schüler ein Verfahren zum Löschen von Knoten in Binärbäumen beschreiben können. Dieses Lernziel kann man auf zweierlei Weisen erreichen, und entsprechend formuliere ich die nächste Übung, die wieder als Alternativ-Übung anzusehen ist. Die Programmier-Cracks unter Ihnen versuchen sich an einem funktionierenden Quelltext zum Löschen, und die eher an einem erfolgreichen Abitur interessierten Schüler erstellen eine Powerpoint-Präsentation zum Löschen.

Übung 19.9-A (11 Punkte)

Erweitern Sie die Klasse Tree um vier Methoden zum Löschen von Elementen. Drei private-Methoden delete1(), delete2() und delete3() (1, 2 bzw. 3 Punkte), die die drei im Text genannten Fälle abdecken, sowie eine public-Methode delete(), welche die zu löschende Zahl sucht (2 Punkte) und dann entscheidet, welche der drei private-Methoden aufzurufen ist (1 Punkt). Falls Sie das Ganze auch noch am PC zum Laufen bringen, erhalten Sie zusätzliche 2 Punkte.


Übung 19.9-B (6 Punkte)

Erstellen Sie eine Powerpoint-Präsentation zum Löschen von Elementen in Bäumen. Die Zeichnungen der Bäume fertigen Sie bitte mit den Powerpoint-eigenen Mitteln an. Auf gar keinen Fall dürfen Sie die auf dieser Website veröffentlichen Graphiken verwenden (es sei denn, Sie wären mit nur 1 Punkt einverstanden).


Lösungshinweise zu allen Übungen der Buchversion finden Sie in dem Lehrerband, den Sie von mir gegen einen kleinen Unkostenbeitrag erhalten können.

Die Übungen der Buchversion unterscheiden sich teils erheblich von den hier veröffentlichen Übungen. Das liegt daran, dass ich die Folge 19 für die Buchversion völlig überarbeitet habe. Sehr schwere Aufgaben sind ganz herausgenommen worden, einige Aufgaben sind umformuliert worden, bei einigen Aufgaben wurde das Bewertungsschema angepasst, weil ich nämlich beim Lösen erst selbst gemerkt habe, wie schwer manche Aufgaben in Wirklichkeit sind, und einige Aufgaben sind auch ganz neu dazugekommen.

Diese Webseite über Bäume wird nicht weiter entwickelt. Statt dessen können Sie die Buchversion des Skriptes gegen gleichwertiges Tauschmaterial oder einen kleinen Unkostenbeitrag Ivon mir erhalten. Schreiben Sie mir eine E-Mail, wenn Sie Interesse haben.

Die Lösungen zu den Übungen finden Sie in dem Lehrerband, den ich zur Zeit erarbeite.

und weiter mit 19.7 - Implementierung von Bäumen mit Hilfe von Arrays

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 19. April 2006





IMPRESSUM