Fixierung von Zeigern in der Löschfunktion eines Binärbaums (Knoten mit 2 Kindern)

Question

Ich bin mit ein wenig Mühe denken, wie zum Teufel ich die entsprechenden Zeiger zu beheben, wenn Sie versuchen, einen Knoten aus einem binären Baum zu löschen, wo dieser Knoten 2 Kinder hat.

Ich verstehe das Grundkonzept, und ich bin im Grunde nur mit Schwierigkeiten bei der Festsetzung der Zeiger ...

Also, im Grunde ist meine Löschfunktion größtenteils fertig und jeder Fall funktioniert bereits (soweit meine umfangreichen Tests gehen, alles funktionierte OK), ich bin nur der Fall-Knoten mit 2 Kindern fehlt. Nehmen wir an, wir befinden uns innerhalb der else if die sich mit diesem Fall befasst:

Ich werde dort 2 Zeiger haben, currPtr der den zu löschenden Knoten enthält, prevPtr der den übergeordneten Knoten enthält. Ich habe auch eine Variable namens fromLeft die definiert, ob die currPtr Elternteil kommt von dem linken oder rechten Zeiger auf prevPtr . Dann habe ich einen Aufruf einer anderen Funktion namens extractMin(Tree *t) der den niedrigsten Wert im Baum extrahiert. Wenn ich diese Funktion mit currPtr->right als Argument, den Nachfolger von currPtr aus dem Baum extrahiert werden soll (die Funktion löscht ihn aus dem Baum, fixiert die Zeiger und gibt den Knotenzeiger zurück). Der Nachfolger-Zeiger wird gespeichert auf tempPtr .

Hier ist die Struktur meines Baumes:

typedef int TreeElement;

typedef struct sTree {
   TreeElement item;

   struct sTree *left;
   struct sTree *right;
} Tree;

Und der Code für die Extraktionsfunktion:

Tree *extractMin(Tree *tree) {
    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if(prevPtr) prevPtr->left = currPtr->right;

    // inorder successor
    return currPtr;
}

Der Code oben fehlt der Fall hier der Baum hat nur einen Knoten, der Root-Knoten, wird es nicht richtig funktionieren und es auch nicht überprüfen, ob der Baum hat keine Knoten überhaupt, aber es funktioniert, wenn ein Baum hat ein paar Knoten.

Wie kann ich also die notwendigen Zeiger auf der else if für die Löschung des Knotens? Denken Sie auch daran, dass die left y right Zeiger auf die Baumknoten werden immer irgendwo hinzeigen oder NULL .

Übrigens, ich möchte das iterativ machen.

Answer 1

Aktualisiert: Sie wollen also die Reihenfolge der Knoten beibehalten, indem Sie den Knoten durch seinen direkten Nachfolger oder Vorgänger in der Reihenfolge ersetzen.

Nehmen wir an, der nachstehende Baum ist geordnet. Die Reihenfolge der Knoten ist:

H < D < I < B < J < E < K < A < F < M < C < N < G < O

Sie möchten einen Knoten (A) löschen, der zwei Kinder hat. Sie ziehen entweder den Vorgänger (K) oder den Nachfolger (F) des Knotens anstelle des Originals heran. Wählen wir den Nachfolger. Sie finden ihn folgendermaßen: Sie gehen die linken Kinder von C durch, bis Sie eines finden, das kein linkes Kind hat; dies ist der direkte Nachfolger von A in der Reihenfolge.

       A
   B       C
 D   E   F   G
H I J K   M N O

F wird also nach oben gezogen, und der linke Teilbaum von A wird nicht berührt. Nun sollte aber auch M nach oben gezogen werden, um das linke Kind von C zu werden (dies geschieht in Ihrem extractMin() ).

Nach allen Umlagerungen erhält man

       F
   B       C
 D   E   M   G
H I J K     N O

Im Code ist dies meine Lösung. Ich habe eine NULL-Prüfung zu extractMin() um den Aufrufer-Code zu vereinfachen, so dass ich nicht benötige else if .

Aktualisiert extractMin() für den Fall, dass tree hat keine Kinder.

Tree *extractMin(Tree *parent, Tree *tree) {
    if (!tree) return NULL;

    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if (prevPtr) {
        prevPtr->left = currPtr->right;
    } else if (parent) {
        parent->right = currPtr->right;
    }

    // inorder successor
    return currPtr;
}

// prevPtr is the parent, currPtr is the node to be deleted
Tree *successor = extractMin(currPtr, currPtr->right);
successor->left = currPtr->left;
successor->right = currPtr->right;
if (fromLeft) {
    prevPtr->left = successor;
} else {
    prevPtr->right = successor;
}
// Now currPtr can be destroyed

Beachten Sie, dass dieser Code nicht getestet ist, ich garantiere also für nichts :-)

Beachten Sie, dass wiederholte Löschungen wie diese den Baum unausgewogen machen können (d.h. einige Pfade werden viel länger als die anderen). Binäre Sortierbäume führen Löschungen auf diese Weise durch, verwenden aber auch ein Rebalancing danach, um den Baum nahe am Ideal zu halten (wo jedes Blatt auf der gleichen Ebene ist, wie in meinem ersten Beispiel oben).

Answer 2

Die Antwort aus dem Lehrbuch lautet, den betreffenden Knoten durch seinen äußersten rechten Nachfahren zu ersetzen.

                6
         3             8
     2      4      7      9
   1          5             10

Wenn wir 3 entfernen wollen, können wir sie durch 4 ersetzen und dann 5 in das Loch ziehen, in das 4 hineingegangen ist. Wir können dies immer tun, und es wird die in der Reihenfolge Traversal erhalten.

OK. Wenn man sich Ihren Code ansieht, ist es das, was Sie wollen:

//in your function
    else if (/*has 2 nodes*/) {
        currPtr->item = extractMin(currPtr->right, &(currPtr->right))->item;
    }

Tree *extractMin(Tree *tree, Tree ** back) {
    Tree *currPtr = tree;

    while(currPtr->left) {
        back    = &(currPtr->left);
        currPtr = currPtr->left;
    }

    *back = currPtr->right;

    // inorder successor
    return currPtr;
}

Das Argument ** ermöglicht es uns, den Fall zu behandeln, dass wir das unmittelbare rechte Kind des gelöschten Knotens verwenden:

     3   <--deleting this node
   /   \   <--back points to this edge.
  2     4   <--extractMin is called on this node and returns this node,
         \
          5   <-- (*back) now points to this node. 

Denken Sie an das neue ExtractMin in 2 Fällen.

1. Im ersten Fall wird die Schleife mindestens einmal durchlaufen. Wenn wir prevPtr im Code gelassen hätten, würden wir das nach der Schleife sehen, back == &(prevPtr->left); (z.B. wird durch die Änderung von *back prevPtr->left geändert). Es ist also dasselbe wie bei Ihrem obigen Code.
2. Im zweiten Fall wird die Schleife nicht durchlaufen. In diesem Fall, back verweist auf einen Link, den wir auf keine andere Weise erhalten können (es sei denn, wir ändern extractMin so, dass es eine Ebene höher beginnt).

Eine andere Möglichkeit, darüber nachzudenken, ist, dass (*back) immer auf currPtr zeigt (nehmen Sie sich einen Moment Zeit und überprüfen Sie dies), also zeigt back auf die Kante, die wir ändern müssen, wenn wir currPtr entfernen.

Answer 3

Wenn Sie das ernst meinen, sollten Sie sich die AVL-Bäume ansehen:

http://en.wikipedia.org/wiki/AVL_tree

Sie können schwierig zu implementieren sein, bleiben aber aufgrund der Rotationen, die Sie bei Einfügungen und Löschungen durchführen, ausgeglichen.