RotSchwarzBaum: Löschen mittels insert-Methode

Diskutiere RotSchwarzBaum: Löschen mittels insert-Methode im Allgemeine Java-Themen Bereich.
J

Jakkkob

Hallo zusammen :)
Im Titel steht was ich machen will, meine Hilfsfunktionen funktionieren 100%. Allerdings bekomm ich bei der löschen-Methode immer ein StackOverFlowError.
Grundidee: Ich baue einen neuen Baum mit insert auf, aber ohne den zu löschenden Knoten. Am ende initialisiere ich den eigentlichen Baum mit dem neu erstellten Baum.

Hier ist der Code (Rekursiv):
Java:
    public void delete(TreeNode toDelete) { 
        TreeNode _rootTmp = _root;
        RedBlackTree tree = new RedBlackTree();
        if(_root == null) {
            tree.insert(_root);
        }
        
        if(_rootTmp.left != _nil) {
            if(!_rootTmp.left.equals(toDelete)) {
                tree.insert(_rootTmp.left);
            }
            delete(_rootTmp.left);
        }
        if(_rootTmp.right != _nil) {
            if(!_rootTmp.right.equals(toDelete)) {
                tree.insert(_rootTmp.right);
            }
            delete(_rootTmp.right);
        }
        if(_rootTmp.left == _nil && _rootTmp.right == _nil) {
            _root = tree._root;   
        }
    }
In meiner eigenen RedBlackTree-Klasse behandle ich die Leaves mit _nil (also nicht mit null).
Vielleicht hat ja jemand ne Idee warum das nicht klappt.
LG!
Jakkkob
 
J

Jakkkob

Ich habe nun erkannt dass ich ja bei jedem Rekursionsaufruf einen neuen tree erstelle und root weiterhin die root bleibt. Daher hab ich es versucht in eine Hilfsfunktion auszulagern, jedoch gibt es auch hier ein StackOverFlow error, also wird auch hier die Rekursion NICHT abgebrochen:

Java:
    public void delete(TreeNode toDelete) {
        TreeNode _rootTmp = _root;
        RedBlackTree tree = new RedBlackTree();
        deleteRec(toDelete, _rootTmp, tree);
    } 
    
    public TreeNode deleteRec(TreeNode toDelete, TreeNode _rootTmp, RedBlackTree tree) {
        
        if(_root == null) {
            tree.insert(_root);
        }
        
        if(_rootTmp.left != _nil) {
            if(!_rootTmp.left.equals(toDelete)) {
                tree.insert(_rootTmp.left); 
            }
            deleteRec(toDelete, _rootTmp.left, tree);
        }
        if(_rootTmp.right != _nil) {
            if(!_rootTmp.right.equals(toDelete)) {
                tree.insert(_rootTmp.right);
            }
            deleteRec(toDelete, _rootTmp.right, tree);
        }
        if(_rootTmp.left == _nil && _rootTmp.right == _nil) {
            return _root = tree._root;   
        }
        return tree._root;
    }
 
mihe7

mihe7

Man kann es nicht 100 %-ig erkennen, aber ich denke, das Hauptproblem des Ansatzes dürfte sein, dass die Knoten keine einzelnen Knoten, sondern Wurzelknoten ganzer Teilbäume sind. Wenn Du also einen Baum der Höhe 3 (inkl. Wurzel) annimmst und es sich bei dem zu löschenden Knoten um einen Blattknoten handelt, dann fügst Du diesen bereits im ersten Schritt zum neuen Baum hinzu (weil der zu löschende Knoten im linken oder rechten Teilbaum der Wurzel verortet ist).
 
J

Jakkkob

Man kann es nicht 100 %-ig erkennen, aber ich denke, das Hauptproblem des Ansatzes dürfte sein, dass die Knoten keine einzelnen Knoten, sondern Wurzelknoten ganzer Teilbäume sind. Wenn Du also einen Baum der Höhe 3 (inkl. Wurzel) annimmst und es sich bei dem zu löschenden Knoten um einen Blattknoten handelt, dann fügst Du diesen bereits im ersten Schritt zum neuen Baum hinzu (weil der zu löschende Knoten im linken oder rechten Teilbaum der Wurzel verortet ist).
Oh mist da hast du natürlich recht! Hast du eine Idee wie ich das dennoch auf diese Art machen könnte?
 
J

Jakkkob

Hallo, ich habs jetzt mal so probiert, sodass der Node mit keinen anderen Nodes verknüpft ist.
Hier der Code (tut aber wieder nicht, Endlosschleife)
Java:
public void delete(TreeNode toDelete) {
        TreeNode _rootTmp = _root;
        RedBlackTree tree = new RedBlackTree();
        deleteRec(toDelete, _rootTmp, tree);
    } 
    
    public TreeNode deleteRec(TreeNode toDelete, TreeNode _rootTmp, RedBlackTree tree) {
        
        TreeNode tmp = new TreeNode(_nil, _nil, null, _rootTmp.key, _rootTmp.color, _rootTmp.value);
        if(_root == null) {
            tree.insert(tmp);
        }
        
        if(_rootTmp.left != _nil) {
            if(!_rootTmp.left.equals(toDelete)) {
                tree.insert(tmp);   
            }
            deleteRec(toDelete, _rootTmp.left, tree);
        }
        if(_rootTmp.right != _nil) {
            if(!_rootTmp.right.equals(toDelete)) {
                tree.insert(tmp);
            }
            deleteRec(toDelete, _rootTmp.right, tree);
        }
        if(_rootTmp.left == _nil && _rootTmp.right == _nil) {
            return _root = tree._root;   
        }
        return tree._root;
    }
LG
 
mihe7

mihe7

Oh mist da hast du natürlich recht! Hast du eine Idee wie ich das dennoch auf diese Art machen könnte?
Naja, es ergibt sich natürlich das Problem, dass die Färbung hinterher nicht mehr stimmt.

Unabhängig davon, was die Rekursion betrifft, so ist die Überlegung doch folgende: deleteRec(...) liefert die Wurzel eines Baums, der toDelete nicht enthält.

Ausgehend davon gilt für den übergebenen Wurzelknoten in deleteRec:

1. Ist der Knoten null? Gib null zurück.
2. Ist der Knoten gleich toDelete? Dann muss an seine Stelle ein anderer Knoten treten... welcher?
3. Ansonsten ist es einfach: Sei w eine Kopie des übergebenen Wurzelknotens, dann setze w.left = deleteRec(w.left) und w.right = deleteRec(w.right)
4. Gib w zurück
 
J

Jakkkob

Naja, es ergibt sich natürlich das Problem, dass die Färbung hinterher nicht mehr stimmt.

Unabhängig davon, was die Rekursion betrifft, so ist die Überlegung doch folgende: deleteRec(...) liefert die Wurzel eines Baums, der toDelete nicht enthält.

Ausgehend davon gilt für den übergebenen Wurzelknoten in deleteRec:

1. Ist der Knoten null? Gib null zurück.
2. Ist der Knoten gleich toDelete? Dann muss an seine Stelle ein anderer Knoten treten... welcher?
3. Ansonsten ist es einfach: Sei w eine Kopie des übergebenen Wurzelknotens, dann setze w.left = deleteRec(w.left) und w.right = deleteRec(w.right)
4. Gib w zurück
Die Färbung korregiert doch meine insert-methode (Die besitzt eine hilfmethode die die Farben korrigiert).
Ich habs nun versucht wie du sagstest umzusetzen, jedoch endet auch dieser Versuch in einer Endlosschleife. Hier der Code:
Java:
    public void delete(TreeNode toDelete) {
        TreeNode _rootTmp = _root;
        RedBlackTree tree = new RedBlackTree();
        deleteRec(toDelete, _rootTmp, tree);
    } 
    
    public TreeNode deleteRec(TreeNode toDelete, TreeNode _rootTmp, RedBlackTree tree) {
        
        TreeNode tmp = new TreeNode(_nil, _nil, null, _rootTmp.key, _rootTmp.color, _rootTmp.value);
        
        if(toDelete == null) {
            return null;
        }
        if(_root == null) {
            tree.insert(tmp);
        }
          
        if(_rootTmp.left != _nil) {
            if(_rootTmp.left.key != toDelete.key) {
                tree.insert(tmp);   
            }
            _rootTmp.left = deleteRec(toDelete, _rootTmp.left, tree);
        }
        if(_rootTmp.right != _nil) {
            if(_rootTmp.right.key != toDelete.key) {
                tree.insert(tmp);
            }
            _rootTmp.right = deleteRec(toDelete, _rootTmp.right, tree);
        }
        if(_rootTmp.left == _nil && _rootTmp.right == _nil) {
            return _root = tree._root;   
        }
        return tree._root;
    }
Wie gesagt, die Grundidee ist, dass man sukzessiv die Knoten durchgeht, jeweils die nachfolger löscht, mittels insert in einen neuen Baum einfügt (WENN der aktuell betrachtete Node NICHT der toDelete ist), automatisch werden die Farben korrigiert (Hilfsmethode von insert) und schließlich noch der Baum (Wurzel) mit dem neu erstellten Baum initialisiert.
 
mihe7

mihe7

Die Färbung korregiert doch meine insert-methode (Die besitzt eine hilfmethode die die Farben korrigiert).
Ach so... Du fügst ja ein.

Probier mal:

Java:
    public TreeNode deleteRec(TreeNode toDelete, TreeNode _rootTmp, RedBlackTree tree) {        
        if(toDelete == null || _rootTmp == null) {
            return null;
        }

        TreeNode tmp = new TreeNode(_nil, _nil, null, _rootTmp.key, _rootTmp.color, _rootTmp.value);
        if (!toDelete.equals(_rootTmp)) {
            tree.insert(tmp);
        }        

        deleteRec(toDelete, _rootTmp.left, tree);
        deleteRec(toDelete, _rootTmp.right, tree);
        return tmp;
    }
 
J

Jakkkob

Vielen Dank, sieht schon besser aus: Keine Endlosschleife mehr!!
Allerdings besitzt der Baum nach der delete-Methode genau doppelt so viele Elemente wie erwartet.

Hier ein Ausschnitt des betroffenen JUnit-Tests:
Java:
for( int j=0; j<1024; j++ ) {
                        TreeNode node = tree.search(j);
                        assertNotEquals(tree.nil(), node, "Node not found in the tree!");
                        tree.delete(node);   
                    } 
                    
                    System.out.println("Starting tests after deletion...");
                    assertEquals(treeNodes.size()-1024, countElements(tree, tree.root()), "Wrong number of elements in the tree!");
Und der Test schlägt fehl, da 1024 Elemente erwartet werden, der Baum jedoch 2048 Elemente (Nodes) enthält.

Weißt du zufällig woran dies liegen kann?
Vielen Dank!!!
 
mihe7

mihe7

Du müsstest natürlich den neu erzeugten Baum auch verwenden:
Java:
    public void delete(TreeNode toDelete) {
        _root = deleteRec(toDelete, _root, new RedBlackTree());
    }
EDIT: in deleteRec ist noch ein Fehler. Weil Du ja einfügst, müsstest Du tatsächlich die Wurzel von tree zurückgeben und nicht tmp.
 
J

Jakkkob

Jetzt wirft eine countElements Methode im JUnit-Test ne NullpointerExc.

Hier die betroffene Methode:
Java:
protected int countElements(RedBlackTree tree, TreeNode node) {
        if( node == tree.nil() ) {
            return 0;
        }
        return countElements(tree, node.left) + countElements(tree, node.right) + 1;
    }
Sie wird im eben geschickten JUnit ausschnitt aufgerufen.
Beachte dass diese Methode schon fertig implementiert war (also muss der Fehler bei der delete liegen).

Viele Grüße und Dankeschön!
 
J

Jakkkob

Dein Code stimmt nicht 100% mit dem überein was ich machen möchte. Die Methode bleibt ja VOID, da die Objektmethode delete auf eine root ausgeübt wird, dessen baum dann bearbeitet wird. Und am ende sollte man dann die wurzel des Baums (mit dem die Objektmethode aufgerufen wird) mit der root des neu erstellten Baums initialisieren.

LG
 
J

Jakkkob

Dein Code stimmt nicht 100% mit dem überein was ich machen möchte. Die Methode bleibt ja VOID, da die Objektmethode delete auf eine root ausgeübt wird, dessen baum dann bearbeitet wird. Und am ende sollte man dann die wurzel des Baums (mit dem die Objektmethode aufgerufen wird) mit der root des neu erstellten Baums initialisieren.

LG
Ach ne das machst du ja in der delete methode, my bad
 
J

Jakkkob

Mit diesem Code ist es wieder das gleiche Problem, dass man doppelt so viele Elemente drin hat wie gewollt :(

Java:
    public void delete(TreeNode toDelete) {
        _root = deleteRec(toDelete, _root, new RedBlackTree());
    }
      
    public TreeNode deleteRec(TreeNode toDelete, TreeNode _rootTmp, RedBlackTree tree) {       
        if(toDelete == null || _rootTmp == null) {
            return null;
        }

        TreeNode tmp = new TreeNode(_nil, _nil, null, _rootTmp.key, _rootTmp.color, _rootTmp.value);
        if (!toDelete.equals(_rootTmp)) {
            tree.insert(tmp);
        }       

        deleteRec(toDelete, _rootTmp.left, tree);
        deleteRec(toDelete, _rootTmp.right, tree);
        return _rootTmp;
    }
 
mihe7

mihe7

Zip mal den ganzen Schrott. EDIT: Du kannst das Zip hochladen, dann schau ich mir das später an; wird aber etwas dauern.
 
J

Jakkkob

Zip mal den ganzen Schrott.
Da das hier öffentlich ist würde ich ungern mein ganzen Projekt hochladen. Wenn du eine email adresse (z.B. kurz eine trashMail erstellen) reinschickst der ich den Schmodder schicken kann wäre es super.

Danke für das Angebot!
 
Thema: 

RotSchwarzBaum: Löschen mittels insert-Methode

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben