Deletion in einem binären Suchbaum

Question

Der Lehrer erklärte uns diesen Algorithmus, dass er einen Knoten in einem binären Suchbaum löscht, aber ich kann nicht verstehen, wie es funktioniert, wenn der zu löschende Knoten nur ein Kind hat (ich weiß bereits, wie es theoretisch funktioniert).

Algorithmus:

generasacodicetagpre.

Ich möchte beispielsweise die Knotennummer $ 7 $ :

Aber sollte das Endergebnis das nicht sein?

Answer 1

Ihre Wahl ist sicherlich korrekt.

Es ist jedoch nichts falsch mit dem Code Ihres Lehrers. Hier ist ein Auszug von Clrs.

Die Operationen des Einfügens und des Löschens führen dazu, dass das dynamische Satz, der durch einen binären Suchbaum dargestellt wird, zu ändern. Die Datenstruktur muss modifiziert werden, um diese Änderung widerzuspiegeln, aber so hält die Binär-Suchen-Tree-Eigenschaft weiterhin.

Wir bevorzugen sicherlich die Operation auf den einfachsten Weg oder den schnellsten Weg. Es besteht jedoch keine Anforderung, dass die Modifikation auf einfachste Weise oder sogar auf einfache Weise erfolgen muss. Es ist auch nicht erforderlich, dass die Modifikation auf dem schnellsten Weg oder sogar auf jeden Fall hergestellt wird. Alles erfordert, dass der Betrieb des Löschvorgangs einen anderen binären Suchbaum erstellen sollte, der alle Knoten aus dem angegebenen binären Suchbaum ohne diesen bestimmten Knoten (und nicht mehr Knoten mehr aufweist. Wie diese verbleibenden Knoten einen binären Suchbaum bilden, ist völlig frei von Fesseln.

Ihr Lehrercode dagegen ist wahrscheinlich der kürzeste klare Code, der den Job erledigt. Je mehr ich studiere, desto Einfallsreichtum finde ich.

Answer 2

Ihre Zeichnung ist die richtige Lösung, aber Ihre Analyse für Ihren Lehrercode ist jedoch nicht genau (Sie interpretieren den Code)

Wenn ich zuerst gesehen habe, dass Ihr Qi den Code nicht sorgfältig gelesen habe und ich dachte (aus dem 1. PIC / Zeichnen), dass Ihr Lehrer einen Löschvorgang für eine spezielle Art von BST durchführt, der zusätzliche Bedingungen als die relative Reihenfolge hat, Dies ist nicht der Fall

Wenn Sie von einem BST löschen (versuchen Sie versuchen, Ihre Codevariablen zu folgen, ist Z der zu löschende Knoten)

Wenn z ein Blattknoten ist (keine Kinder), ersetzen Sie den übergeordneten Zeiger mit Null

wenn z 1 Kind hat (ob links oder rechts egal ist), wenden Sie den übergeordneten Zeiger auf sein einziges Kind

das ist eine sehr einfache Codierung, in einem SEMI-Pseudo-Code

wenn (z.leg== null) {physisch_delete (z, zlos); Rückkehr(); // Entweder haben wir nur Rechtsunterstützung oder keine }

// Hier sind wir sicher, dass es einen linken Teilbaum gibt

wenn (z. recht== null) {physisch_delete (z, z.left); Rückkehr(); }

// physical_delete hat den Austausch als 2. Parameter, alle Loops in Ihrem Lehrercode ist es, herauszufinden, was es bedeutet, dass wir zwei Teilbetten haben

wenn z 2 kinder hat, dann musst du einen von ihnen wählen, um seinen Platz zu nehmen, und hier kommt dein Lehrercode (nicht im vorherigen Fall)

in ur pic Imagine u r löschen "5" Dieser langjährige Code dient zum Anpassen des verbleibenden Teilbahments seiner beiden Kinder (wie man 7 & 3 & ihre Kinder zum Knoten 12 verbindet, um den BST-Constrain zu halten)

Wenn Sie eine detaillierte Ablaufverfolgung benötigen, können wir dies tun, aber nur, wenn Sie dieses hilfreiche als Start fanden