Rückwärts geführte Rekursion

[MyPiano]

Hallo,

ich arbeite gerade an einem Binärbaum und die Löschfunktion macht mir ein wenig Kummer. Das kopieren der Knoten ist kein Problem, aber das eigentliche Löschen eines Knotens will nicht richtig funktionieren.

So sieht mein Baum in etwa aus. Die Idee ist jetzt, dass ich, wenn ich z.B. das Element 17 löschen will, den linken Subknoten von Knoten 17 kopiere und links an den Knoten anfüge. Soweit klappt das ganze auch noch (siehe Code unten). Das Problem liegt jetzt darin, dass ich den Knoten 17 jetzt löschen will und durch den Knoten 15 ersetzen will. Dazu müsste ich aber Eine Rekursion rückwärts durchführen und mein Verstand sagt mir, dass das nicht funktioniert. Deshalb stellt sich für mich die Frage, wie ich das am besten mache. Hat jemand dazu ne Idee?

                               --------------------------[33]
                              |
                       ----[17]-----
                      |            |
                   -[15]        --[21]------
                  |             |           |
                [12]          [18]       [29]

public void delete(int value) {
        BinaryTree temp = null;
        if (content != null) {
            if (value < content) {
                left.delete(value);
            } else if (value > content) {
                right.delete(value);
            } else if (value == content) {
                temp = right;
                right = null;
                left.right = temp;
            }
        }
    }

 

[Marco13]

So ganz hab' ich nicht verstanden, wie das am Ende aussehen soll (bzw. das was ich verstanden hatte passt nicht zum geposteten Code).

Wenn man so traversiert, wie du im moment, und z.B. Knoten 15 löschen will, dann stellt man ja fest "this.content==15", und müßte dann "this" löschen: Vorher war node17.left==node15, und nachher müßte node17.left==node12 sein. Aber... wenn man erstmal bei node15 ist, kommt man an node17 ja nicht mehr ran.

Ich gehe davon aus, dass man dafür "einen Knoten voraus" schauen muss - also nicht mit "this.content" arbeiten, sonden mit "this.left.content" und "this.right.content". Im Konkreten beispiel: Wenn man 15 löschen würde, würde man traversieren, und bei Konten 17 würde man dann sowas machen wie

if (this.left.content == 15) // node17.left ist node15 - Der muss gelöscht werden
{
    this.left = this.left.left; // node17.left zeigt jetzt auf node12 - und node15 wurde gelöscht
...

Das kann auch ein bißchen komplizierter werden, aber dieses "Vorausschauen" ist wohl ein möglicher Ansatz, den du mal durchdenken könntest...

 

[SlaterB]

> wenn ich z.B. das Element 17 löschen will, den linken Subknoten von Knoten 17 kopiere und links an den Knoten anfüge

du nimmst den linken Subknoten von 17, kopierst ihn (warum?) und setzt ihn dann wieder links von Knoten 17 an,
wo er schon war? oder links an einen anderen Knoten?
klingt seltsam und mit dem Code nicht übereinstimmend, vielleicht verstehe ich etwas falsch,

in einem Binärbaum zu löschen kann ganz schön kompliziert sein, nach
Binärbäume, Suchbäume, Baumsortieren
müsstest du beim Löschen die 17 entfernen und durch die 21 ersetzen,
dort wo die 21 war, muss rekursiv auch ersetzt werden (die 21 wurde quasi gelöscht), die 29 eingefügt werden

 

[Spacerat]

Ich benenne die drei Zweige eines Knotens mal mit "parent", "left" und "right. Wir befinden uns an Position 17 und kennen damit dessen Zweige (15, 33 und 21). Hier holen wir uns die Instanz von Knoten 15 (nein, man kopiere sie nicht!), und setzen dort "parent" = 33 und "right" = 21. Somit tritt 15 an die Stelle von 17. Das Problem, was nun auftreten könnte, ist, das "right" bei 15 bereits gesetzt sein könnte. Dieser Zweig wäre dann auch verloren. Besser wäre es, zunächst den Wert von 17 zu invalidieren (nullsetzen) und den Knoten im Baum zu erhalten wenn er Kindknoten ("left" und oder "right") hat. Wenn der Knoten aufgrund der Tatsache das er keine Kindknoten mehr hat, entfernt werden kann, kann man noch rekursiv (den "parent"s folgend) prüfen welche Knoten ebenfalls entfernt werden können.