TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 15
Löschen Sie aus dem abgebildeten binären Suchbaum in der angegebenen Reihenfolge die Knoten 50, 40 und 8. Zeichnen Sie den Baum nach jeder Löschung eines Knotens.
Entfernen von 50[Bearbeiten | Quelltext bearbeiten]
Da 50 auf beiden Seiten einen Nachfolger hat, muss man den Successor (das nächstgrößere Element) für 50 finden. Das findet man in dem man im rechten Teilbaum von 50 den Knoten nimmt der an der linkesten Stelle steht. Rechter Teilbaum ist hier jener mit der Wurzel 60. Das Element das in diesem Teilbaum an der linkesten Stelle steht ist 55. Jetzt tauscht 50 mit 55 Platz und 50 wird gelöst. Der resultierende Baum sieht so aus:
Entfernen von 40[Bearbeiten | Quelltext bearbeiten]
Da 40 nur einen Nachfolger hat, 55, kann man 40 einfach aus dem Baum entfernen und die zwei "losen" Striche die dadurch entstehen miteinander verbinden. (Alternative: Successor suchen und einfach damit ersetzen). Der resultierende Baum sieht so aus:
Entfernen von 8[Bearbeiten | Quelltext bearbeiten]
Bei 8 ist es das selbe Spiel wie bei 50. Man sucht den Successor für 8, das wäre 10 (linkestes Element, rechter Teilbaum). Jetzt hat 10 blöderweise einen Nachfolger. Glücklicherweise nur einen das heißt, 11 nimmt die Position von 10 ein und wird damit linker Nachfolger von 15. 12 bleibt rechter Nachfolger von 11. 10 ersetzt uns den Knoten 8. Der resultierende Baum sieht so aus:
Lösung von Michael