Java -, Binär-Baum remove-Methode

Ich versuche zu schreiben remove(node cRoot, Object o) Funktion für einen sortierten binären Baum.

Hier ist was ich habe, so weit:

private boolean remove(Node cRoot, Object o) {
  if (cRoot == null) {
    return false;
  }
  else if (cRoot.item.equals(o)) { 
    //erase node fix tree
    return true;
  }
  else if (((Comparable)item).compareTo(cRoot.item)<=0){
    return remove(cRoot.lChild, o);
  }
  else { 
     return remove(cRoot.rChild,o);
  }
}

Funktioniert es nicht richtig. Um einen node zu löschen, die Sie reparieren müssen, den Baum zu fixieren das Loch. Wie sollte dies gemacht werden?

Der Baum beheben wird, hängt vom Algorithmus, die Sie verwenden, um die balance der Baum.

InformationsquelleAutor user101934 | 2009-05-07

4

Grundsätzlich gibt es zwei Möglichkeiten der Durchführung einer entfernen auf dem Baum:

Erste Methode:

Entfernen den Knoten, dann ersetzen Sie es entweder mit Kind. Dann, resort-der Baum by doing-Eltern-Kind-swapping, bis der Baum wieder sortiert.

Die zweite Methode:

Traverse den Baum zu finden, den nächsten (höchsten oder niedrigsten) Wert, gehört als root*, wenn es ein Blatt ist Knoten, der swap, die mit der Wurzel, dann schneiden Sie den Wert, den Sie entfernen möchten. Wenn es einen internen Knoten suchen, müssen Sie rekursiv aufrufen entfernen, die auf diesem Knoten. Wiederholen Sie, bis ein Blatt-Knoten wird entfernt.

*Was ich meine ist, wenn Sie konvertieren Sie Ihre BST in einer sortierten Liste, dann werden Sie wollen, wählen Sie entweder den Wert Links oder rechts von der Wurzel die neue Wurzel. I. e. weitesten Links stehende Kind des rechten teilbaums oder rechts, die meisten Kinder von den linken Teilbaum.

Erste Methode - was passiert, wenn ein Knoten Kinder hat, die auf beiden Seiten?
Zweite Methode - was Sie tun möchten, ist zu finden die nächst größeren Knoten (z.B. rechts, dann nach Links so weit wie Sie können) und swap-Wert mit ihm. Er wird nur eine oder keine Kinder, damit kann man dann aufheben, das element direkt. Keine Wiederholung erforderlich ist.
1. Methode, die Sie verwenden, um eine Konvention, die entweder immer vertauschen Links oder rechts, Knoten, und verwenden Sie die anderen Knoten, wenn keine vorhanden ist. 2. Methode, nicht unbedingt, es ist möglich, dass die linken Knoten des rechten teilbaums kann eine richtige sub-Baum mit Werten größer als er.

InformationsquelleAutor z -
2

Den grundlegenden pseudo-code für das löschen eines Knotens aus einem sortierten Baum ist ziemlich einfach:
1. löschen den Knoten mit dem Wert
2. finden untergeordneten Knoten mit dem maximalen Wert
3. machen es der root-Knoten
4. wenn Sie Kinder hatten - springen 2 rekursiv
Im Grunde, was Sie tun, ist die sprudelnden Knoten oben auf dem Baum, jedes mal, wenn das maximum der Kinder-Knoten in jedem Knoten, so dass am Ende Sie bleiben mit einem sortierten Baum, und nur ein Knoten fehlt am Ende den vollständigen Pfad, den Sie ging.

Auch - siehe wikipedia zum Thema, haben Sie einige Beispiel-code in C sowie.

Das maximale Kind wird nur eine oder keine Kinder; Sie brauchen nicht zu springen 2 rekursiv. Sie können einfach die Verknüpfung der maximalen Kind, nachdem Sie Sie kopiert haben, seinen Wert in die ursprüngliche Löschung Knoten.

InformationsquelleAutor Yuval Adam
1

In der einfachen case3 Sie können neben-Algorithmus:
```
if(removed node had left child)
{
   place left child instead of removed node;
   most_right = most right leaf in the left subtree;
   move right child of removed node as right child of most_right;
}
else
{
   place right child instead of removed node
}
```
In komplizierter Fall, müssen Sie möglicherweise ein neues Gleichgewicht Ihrer Struktur (siehe AVL-Bäume, http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html für Beispiel C++)

PS entschuldigen Sie meine Deutsch 🙂
AVL-Bäume benötigen ein rebalancing-scan auf jeden - Knoten entfernen, außer, dass ich denke, wo der Knoten ist ein Blatt und der Eltern, nach dem entfernen hat sich ein balance-Faktor von 1 oder -1 (z.B. wenn der Knoten ein Blatt ist und einen Bruder hat).

InformationsquelleAutor Alex
0
1. Blatt-Knoten löschen
2. 1-Kind-Förderung der Teilbaum
3. 2-Kind-Fall, ersetzen Sie den Knoten mit entweder
4. um Nachfolger oder Vorgänger
5. am weitesten Links in der rechten Teilbaum oder
6. am weitesten rechts im linken Teilbaum
Versuchen Formatierungen Ihrem Kommentar als code, es werden die Lesbarkeit zu verbessern.

InformationsquelleAutor user101934

Fand ich diesen code auf Habrahabr. Ich habe nur kommentiert.

public void remove (T1 k){
    Node<T1,T2> x = root, y = null;
    //from while to if(x == null) - searching for key
    while(x != null){
        int cmp = k.compareTo(x.key);
        if(cmp == 0){
            break;  //quit cycle if key element is found
        } else {
            y = x;
            if(cmp < 0){
                x = x.left;
            } else {
                x = x.right;
            }
        }
    }
    if(x == null) return;   //if key is not found or tree is empty
    if(x.right == null){    //if element found has not right child
        if(y == null){      //if element found is root & has not right child
            root = x.left; 
        } else {            //if element found is not root & has not right child           
            if(x == y.left) y.left = x.left;    
            else y.right = x.left;              
        }
    } else {            //element found has right child, so search for most left of rights
        Node<T1,T2> mostLeft = x.right;
        y = null;
        while(mostLeft.left != null) {
            y = mostLeft;
            mostLeft = mostLeft.left;
        }
        if(y == null){  //if right child of element found has not left child
            x.right = mostLeft.right;
        } else {        //if right child of element found has left child
            y.left = mostLeft.right;
        }
        x.key = mostLeft.key;       
        x.value = mostLeft.value;   
    }
}

InformationsquelleAutor guzoff

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.