rekursives Einfügen: Algorithmus

Einfügen mit Bleistift und Papier

Bevor wir das Einfügen von Elementen in einen vorhandenen binären Suchbaum implementieren, wollen wir uns das Prinzip des Einfügens klarmachen. Stellen wir uns vor, wir hätten bereits folgenden binären Suchbaum konstruiert:

Ein einfacher binärer Suchbaum
Autor: Ulrich Helmich 2018, Lizenz: siehe Seitenende.

Es soll nun die Zahl 40 eingefügt werden. Als erstes vergleichen wir die 40 mit der Wurzel des Baumes und kommen zu dem Ergebnis, dass 40 kleiner ist als 100. Also wissen wir jetzt, dass die 40 in dem linken Teilbaum der 100 untergebracht werden muss. Die andere Hälfte des Baums können wir also ignorieren.

Wir vergleichen die 40 nun mit der Wurzel des linken Teilbaums, die den Wert 50 hat. Da 40 < 50 gilt, machen wir mit dem linken Teilbaum der 50 weiter und vergleichen die 40 mit Wurzel des linken Teilbaums der 50, also mit der 33. Nun ist die 40 nicht kleiner als die 33, also machen wir mit dem rechten Teilbaum der 33 weiter.

Hat die 33 überhaupt einen rechten Teilbaum, in der Graphik ist doch nichts mehr zu sehen?

Erinnern wir uns an die rekursive Definition des Begriffs Baum:

Ein Baum ist entweder leer oder besteht aus einem Baum mit mindestens zwei Nachfolgern.

Der Knoten 33 hat in der Tat zwei Nachfolger, allerdings handelt es sich bei diesen beiden Nachfolgern um leere Bäume. Graphisch könnte man dies durch Pfeile darstellen, die auf den Wert null zeigen.

Wir können jetzt den rechten leeren Nachfolger der 33 durch das neue Element 40 ersetzen. Umgangssprachlich kann man auch sagen, dass die 40 einfach rechts an die 33 angehängt wird:

Der Suchbaum wird um die 40 erweitert
Autor: Ulrich Helmich 2018, Lizenz: siehe Seitenende.

Die 33 wird durch das Einfügen der 40 zu einem Halbblatt. Würden wir jetzt noch die 20 einfügen, so hätte die 33 auch noch einen linken Nachfolger.

Der Einfüge-Algorithmus

Bevor wir jetzt zur Implementation eines solchen Einfüge-Algorithmus in Java kommen, wollen wir uns den Algorithmus noch einmal näher anschauen.

Flussdiagramm zum Einfügen in einen binären Suchbaum
Autor: Ulrich Helmich 2018, Lizenz: siehe Seitenende.

Das obige Flussdiagramm ist eigentlich recht eindeutig.

1. Ein Hilfszeiger aktuellerKnoten wird zunächst auf die Wurzel gesetzt des gesamten Baums gesetzt.
2. Vergleich des neuen Wertes mit dem Wert des aktuellen Knotens.
3. Wenn der neue Wert kleiner ist als der Wert des aktuellen Knotens, wird nachgeschaut, ob ein linker Nachfolger des aktuellen Knotens existiert.
4. Ist das nicht der Fall, kann der neue Wert direkt als linker Nachfolger des aktuellen Knotens eingefügt werden.
5. Hat der aktuelle Knoten aber einen linken Nachfolger, so wird der Hilfszeiger aktuellerKnoten auf diesen linken Nachfolger gesetzt, und
6. der Algorithmus beginnt eine "neue Runde", startet also wieder bei 1. Allerdings zeigt aktuellerKnoten jetzt nicht mehr auf die Wurzel des gesamten Baums, sondern auf die zuletzt besuchte Wurzel eines Teilbaums.
7. Nochmal zurück zu Punkt 2. Ist der neue Wert nicht kleiner als der aktuelle Wert, so wird der gleiche Algorithmus durchgeführt, allerdings diesmal für den rechten Teilbaum von aktuellerKnoten.