Binäre Suchbäume: Löschen eines Knoten

Das Löschen eines Knoten in einem binären Suchbaum bedingt eine Fallunterscheidung. Je nach Fall ist das Vorgehen einfach oder etwas komplexer.

Erster Fall: Der zu löschende Knoten ist ein Blatt

Setze Referenz des Vaterknotens dieses Blattes zu dem Blatt auf null.

Zweiter Fall: Es gibt genau einen Nachfolger

-       Suche und finde den zu löschenden Knoten.

-       Setze Kindknoten des zugehörigen Vaterknotens auf den nicht-leeren Nachflger des zu löschenden Knotens

Dritter Fall: Knoten hat zwei Nachfolger

-       Suche und finde den zu löschenden Knoten

-       Ersetze zu löschenden Knoten durch größten Knoten des linken Teilbaums

-       Setze Referenz des Vaters des ”aufgestiegenen” Knoten auf Kindknoten gleich null.

Realisierung in Pseudocode:

//Achtung: Dies ist nur pseudocode!

/** Erster Fall: Der zu löschende
Knoten ist ein Blatt*/

vater.links = null; //Knoten ein linkes Kind
vater.rechts = null; // -"- rechtes Kind

/** Zweiter Fall: Der zu löschende
Knoten hat genau ein Kind*/

if(kind.links!=null){
   vater.links = kind.links;
}else{
   vater.links = kind.rechts;
}

/**Dritter Fall: Knoten hat 2 Kinder*/

g = kind.links;
vg = k;

while(g.rechts!=null){
    vg = g;
     g = g.rechts;
}

vater.links = g;