Binärer Suchbaum Knoten rauslöschen

[Cassy3]

Hey Leute, ich bin neu hier, also seht es mir nach, dass der Post evtl. nicht so schön aussieht.
Im Endeffekt steht meine Aufgabe schon hier drüber.
Ich habe einen Binären Suchbaum erstellt und befüllt. Übersichtshalber lasse ich den Code weg.
Nun will ich einen Knoten entfernen, der die selbe Nummer hat wie der als Number übergebene Parameter.

Hier mein Lösungsansatz:
public BinaryTreeNode search(int number, BinaryTreeNode post, BinaryTreeNode prev) {

if (post.getNumber()==number && post==top) {
top=top.getSmaller();
}

else if (post.getNumber()==number && post.equals(prev.getSmaller())) {
if (prev.getSmaller().getSmaller()==null) {
prev.setSmaller(null);
}

else {
prev.setSmaller(prev.getSmaller().getSmaller());
}
}

else if (post.getNumber()==number && post.equals(prev.getLarger())) {
if (prev.getLarger().getLarger()==null) {
prev.setSmaller(null);
}

else {
prev.setLarger(prev.getLarger().getLarger());
}
}

else if (post==top){
search (number,post=post.getSmaller(),prev=top);
search (number,post=post.larger,prev=top);
}

else {
search(number, post=post.getSmaller(),prev=prev.getSmaller());
search(number, post=post.getLarger(),prev=prev.getLarger());
}

return null;
}

Ich bin mir zeimlich sicher, dass ich wieder Code für Code geschrieben habe und dann gibt es eine Simple Lösung, auf die ich einfach nicht komme.
Ich hoffe, ihr Könnt mir helfen und danke für jede Antwort. 🙂

 

[mihe7]

Bitte Code-Tags benutzen (im Editor auf </> klicken).

Zum Problem: ein binärer Suchbaum besteht aus einem Wurzelknoten, sowie möglicherweise aus einem linken und rechten Teilbaum, der selbst ein binärer Suchbaum ist. Im linken Teilbaum stehen die Werte, die kleiner (oder gleich) dem Wert im Wurzelknoten sind, im rechten Teilbaum analog die größeren Werte. Jeder Knoten in einem Baum ist die Wurzel eines Teilbaums. Das sind alles schöne, rekursive Eigenschaften.

Schauen wir uns mal die Ergebnisse an. Was passiert grob, wenn man einen Wert entfernt?

1. Ist der Baum leer, bleibt er leer.
2. Enthält der Baum den Wert nicht, bleibt er unverändert.
3. Enthält der Baum den Wert, dann gibt es einen Knoten k mit diesem Wert, der entfernt werden muss. Der Teilbaum, dessen Wurzel k war, erhält somit eine neue Wurzel oder ist nach dem Löschen leer.
4. Enthält der Baum nur den Wert, dann ist der Baum nach dem Löschen des Werts leer.

Interessant ist vor allem, dass beim Löschen im Baum der alte Teilbaum ggf. eine neue Wurzel erhält. Das können wir nutzen, indem wir sagen: das Löschen liefert den Wurzelknoten des ggf. geänderten Baums:

BinaryTreeNode remove(BinaryTreeNode root, int valueToRemove) {
    BinaryTreeNode newRoot = root;
    return newRoot;
}

Soweit, so gut. Punkt 1 einbauen - das ist trivial und überspringe ich gleich mal. Als nächstes überlegen wir uns, dass es nur zwei Möglichkeiten gibt: entweder enthält root den Wert oder eben nicht. Wenn nicht, können wir anhand des Werts von root entscheiden, ob sich der zu löschende Wert im linken oder rechten Teilbaum befinden muss. An der Stelle nicht vergessen: wir bekommen für den jeweiligen Teilbaum ggf. einen neuen Wurzelknoten zurück...

BinaryTreeNode remove(BinaryTreeNode root, int valueToRemove) {
    if (root == null) {
        return null;
    }

    BinaryTreeNode newRoot = root;
    if (root.getValue() == valueToRemove) {
        // TODO
    } else if (root.getValue() < valueToRemove) {
        BinaryTreeNode newRight = remove(root.getRight(), valueToRemove);
        root.setRight(newRight);
    } else {
        BinaryTreeNode newLeft = remove(root.getLeft(), valueToRemove);
        root.setLeft(newLeft);
    }
    return newRoot;
}

Was aber, wenn root nun den Wert enthält? Bezogen auf root gibt es vier Möglichkeiten:

root hat

a) keinen Teilbaum
b) nur einen linken Teilbaum
c) nur einen rechten Teilbaum
d) einen linken und einen rechten Teilbaum


Gut, a) ist einfach: kein Teilbaum -> dann ist die neue Wurzel null
b) die Wurzel des linken Teilbaums bildet die neue Wurzel
c) die Wurzel des rechten Teilbaums bildet die neue Wurzel
d) wir müssen den Wert in der Wurzel durch seinen Vorgänger oder seinen Nachfolger ersetzen

Bei d) ist es egal, wofür man sich entscheidet. Ich nehme mal den Nachfolger, das ist der Wert des im am weitest links stehenden Knotens im rechten Teilbaum.

Den Code können wir ein wenig umbauen (newRoot brauchen wir nicht mehr) und alle Fälle sofort implementieren:

BinaryTreeNode remove(BinaryTreeNode root, int valueToRemove) {
    if (root == null) {
        return null;
    }

    if (root.getValue() == valueToRemove) {
        if (root.getLeft() == null) {
            return root.getRight();
        } else if (root.getRight() == null) {
            return root.getLeft();
        } else {
            int smallest = findSmallestValue(root.getRight());
            BinaryTreeNode newRight = remove(root.getRight(), smallest);
            root.setValue(smallest);
            root.setRight(newRight);
        }
    } else if (root.getValue() < valueToRemove) {
        BinaryTreeNode newRight = remove(root.getRight(), valueToRemove);
        root.setRight(newRight);
    } else {
        BinaryTreeNode newLeft = remove(root.getLeft(), valueToRemove);
        root.setLeft(newLeft);
    }
    return root;
}

int findSmallestValue(BinaryTreeNode root) {
    if (root.getLeft() == null) {
        return root.getValue();
    }
    return findSmallestValue(root.getLeft());
}

Wenn ich jetzt keinen Gedankenfehler drin hatte, sollte das in etwa funktionieren.