Wie lösche ich einen Knoten aus dem BST-Baum mit 2 Kindern?

Question

ich googled, liest mehrere Tutorials und sah mehrere BST-Node-Löschalgorithmus-Erklärungen an, bevor er diese Frage veröffentlichte. Aus irgendeinem Grund kann ich keine vollständige Erklärung von BST-Knotenlöschalgorithmen finden.

Ich habe 4 Algorithmen gefunden, um den Knoten mit 2 Kindern aus binärer Suchbaum zu entfernen:
1) Finden Sie den kleinsten Knoten vom rechten Subbaum und ersetzen Sie es durch den Knoten, den wir löschen möchten.
2) Finden Sie den größten Knoten vom linken Subbaum und ersetzen Sie es durch den Knoten, den wir löschen möchten.
3) Finden Sie den tiefsten Linksknoten vom rechten Unterbaum und ersetzen Sie es durch den Knoten, den wir löschen möchten.
4) Finden Sie den tiefsten rechten Knoten vom linken Subbaum und ersetzen Sie es durch den Knoten, den wir löschen möchten.

Anscheinend arbeitet keiner dieser Algorithmen für den nächsten Anwendungsfall (höchstwahrscheinlich, weil ich etwas fehlt oder etwas nicht verstehe). Der Anwendungsfall besteht darin, Element 5 vom nächsten Baum zu entfernen:

Für den ersten Algorithmus wählten wir Element 6 und würde den rechten Subbaum verlieren. Für den zweiten Algorithmus wählten wir Element 4 aus und würden den linken Subbaum verlieren. Für den 3. Algorithmus wählten wir Element 7 aus und würden die BST-Regeln verletzen. Für den 4. Algorithmus wählten wir das Element 3, das auch die BST-Regeln verletzen würde.

Wie ist der richtige Algorithmus für einen solchen Anwendungsfall?

Answer 1

Sie sind recht, in BST in der Regel der Fall, in dem ein Knoten zwei Kinder hat, auf den Fall, in dem ein Knoten ein Kind hat, reduziert wird.

Betrachten Sie einen Knoten mit zwei Kindern. Tauschen Sie diesen Knoten mit seinem Vorgänger in der BST (das ist der rechte Knoten im linken Teilbaum), oder - total symmetrisch-- Swap mit dem Nachfolger (der linke Knoten im rechten Teilbaum).

Der zu entfernende Knoten hat auf den meisten ein Kind (falls wir für den Vorgänger gingen, kann es kein richtiges Kind haben). Wenn es keine Kinder hat, löschen wir den Knoten, und wir sind fertig.

Falls der Knoten ein einziges Kind hat, entfernen wir den Knoten und ersetzen sie durch seinen Teilbaum. Wir erhalten wieder einen BST.

In Ihrem Beispiel möchten wir 5 entfernen und mit seinem Vorgänger anwenden. Jetzt ist 4 in der Wurzel, und 5 hat das Kind verlinkt 3. Schließlich entfernen wir 5 und setzen sein Kind 3 an seiner Stelle. Jetzt ist 3 das richtige Kind von 2.

ps. Diese Methode wird manchmal als "Deletion durch Kopieren" bezeichnet, da Werte von einem Knoten in einen anderen kopiert werden. Einige genehmigen diesen Prozess aus zwei Gründen nicht. Das erste Kopieren könnte ein teurer Betrieb sein, und zweite Referenzen gehen verloren (wenn eine andere Datastruktur auf einen Knoten mit einem bestimmten Wert zeigt). Stattdessen ändert man nur die Zeiger.