RotSchwarzBaum: Löschen mittels insert-Methode

Jakkkob

Mitglied
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
 

Jakkkob

Mitglied
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

Top Contributor
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).
 

Jakkkob

Mitglied
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?
 

Jakkkob

Mitglied
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

Top Contributor
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
 

Jakkkob

Mitglied
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

Top Contributor
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;
    }
 

Jakkkob

Mitglied
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

Top Contributor
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.
 

Jakkkob

Mitglied
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!
 

Jakkkob

Mitglied
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
 

Jakkkob

Mitglied
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
 

Jakkkob

Mitglied
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;
    }
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M löschen in Rot Schwarz Bäumen Allgemeine Java-Themen 6
M lineare Sondierung löschen Allgemeine Java-Themen 2
A Sicheres Löschen von Dateien Allgemeine Java-Themen 7
E Varialbe komplett Löschen Allgemeine Java-Themen 26
O Warum kann ich so keine Elemente löschen und erhalte einen IllegalStateException? Allgemeine Java-Themen 4
J ArrayList, ganze Zeilen löschen oder überspringen Allgemeine Java-Themen 4
glamdring273 Discord JDA, Kanal löschen Allgemeine Java-Themen 0
G Java Editor Löschen doppelter Zahlen einer Liste Allgemeine Java-Themen 2
D Input/Output Zwischen zwei ID-Räumen unterscheiden und Objekt löschen Allgemeine Java-Themen 16
L Objekt aus Objekt-array "löschen" Allgemeine Java-Themen 2
X Größten Werte in meinem Array löschen? Allgemeine Java-Themen 16
P Erste Schritte Dateien löschen Allgemeine Java-Themen 4
S Einzigartigen String in Datenbank finden und löschen Allgemeine Java-Themen 23
J Datei löschen, die Leerzeichen im Pfad hat Allgemeine Java-Themen 5
R Index in einem Array löschen Allgemeine Java-Themen 10
R Index in einem Array löschen Allgemeine Java-Themen 2
A Referenzen von Bildobjekten löschen Allgemeine Java-Themen 0
I PDF freigeben zum löschen Allgemeine Java-Themen 4
P Löschen eines keys in einer SortedMap Allgemeine Java-Themen 5
P JDK installieren Kann man die Ordner in C:\Users\*\AppData\LocalLow\Sun\Java\.... löschen? Allgemeine Java-Themen 3
X Löschen von einer Zeile in einer Text Datei. Klappt nicht. Allgemeine Java-Themen 4
J Java - Zeile aus Text datei löschen Allgemeine Java-Themen 13
W Arraylist Text Suchen und Datei löschen Allgemeine Java-Themen 5
G Datei löschen Allgemeine Java-Themen 8
R LinkedList und Threads: Strukturprobleme bez. löschen von Elementen Allgemeine Java-Themen 3
Bluedaishi Dateien löschen die älter als das aktuelle Datum sind Allgemeine Java-Themen 9
L Doppelte eintraege im Stringbuffer löschen Allgemeine Java-Themen 4
J Doppelte Buchstaben löschen - letztes Wort macht er nicht Allgemeine Java-Themen 2
M lucene suchen/löschen/hinzufügen Allgemeine Java-Themen 4
R Leere Verzeichnisse löschen Allgemeine Java-Themen 11
S Speichern/Laden/Hinzufügen/Löschen der Array-Wörter; unerwartete Ausgabe Allgemeine Java-Themen 6
V System.out.println an jeder Stelle im Projekt löschen Allgemeine Java-Themen 4
M Batch zum Java Cache löschen Allgemeine Java-Themen 3
R Löschen von Files nicht möglich Allgemeine Java-Themen 11
KrokoDiehl Verzeichnisse via FileVisitor löschen Allgemeine Java-Themen 3
V Objekt löschen Allgemeine Java-Themen 7
127.0.0.1 StringBuffer leere Zeile löschen Allgemeine Java-Themen 8
J char-Array löschen Allgemeine Java-Themen 5
W n:m Beziehung Referenzen löschen Allgemeine Java-Themen 5
127.0.0.1 Zeilen in .txt Datei löschen Allgemeine Java-Themen 11
D Löschen-Methode im Stapelverarbeitungsprogramm Allgemeine Java-Themen 4
S JTable und Spalten löschen Frage Allgemeine Java-Themen 5
EnHancEd[] ArrayList gezielt löschen Allgemeine Java-Themen 9
S Nullen aus Array löschen Allgemeine Java-Themen 10
N Java lässt sich nicht löschen! Allgemeine Java-Themen 7
U Wie kann mit einen Java Applet Dateien erstellen,verschieben und löschen? Allgemeine Java-Themen 9
P Input/Output Ordner löschen --> geht nicht Datei --> Ja Allgemeine Java-Themen 6
K Leerzeiilen aus ArrayList löschen?! Allgemeine Java-Themen 7
M Objekt aus Liste in Liste suchen/löschen Allgemeine Java-Themen 6
S Singleton Instanz löschen Allgemeine Java-Themen 5
Z Ausschneiden, Kopieren, Einfügen, Löschen in JTextArea Allgemeine Java-Themen 5
K Java Feld Duplikate löschen Allgemeine Java-Themen 5
F SAXBuilder blockiert löschen von Dateien Allgemeine Java-Themen 2
L Datei sicher löschen/mehrfach überschreiben? Allgemeine Java-Themen 2
S Java komplett löschen und neu installieren Allgemeine Java-Themen 4
N Java geht nicht mehr zu löschen Allgemeine Java-Themen 5
E Regex alles nach ? löschen Allgemeine Java-Themen 4
I Über eine Liste iterieren und Objekte löschen. Wie löst man das sauber? Allgemeine Java-Themen 5
W 2D-Grafik nach getthumbnail läst sich Quellbild nicht mehr löschen Allgemeine Java-Themen 3
E Regex HTML Tag und Inhalt löschen Allgemeine Java-Themen 4
S Zeilen in einer Datei löschen Allgemeine Java-Themen 3
Z aus private List<???> list eintrag löschen Allgemeine Java-Themen 4
C Zeile aus einer CSV-Datei löschen Allgemeine Java-Themen 3
J Element aus HashSet löschen Allgemeine Java-Themen 2
S Element aus ArrayListe löschen --> Thread hängt sich auf Allgemeine Java-Themen 2
A LinkedList Auslesen und Objekt Löschen Allgemeine Java-Themen 4
G Mit Batch-Datei verzeichnisse löschen Allgemeine Java-Themen 9
K von List getSelected auf ResultSet Datenbank löschen Allgemeine Java-Themen 2
S Reihen aus einem 2-dim. Array 'löschen' Allgemeine Java-Themen 2
K Threading - schreiben auf Hashmap/löschen - ConcurrentModificationException Allgemeine Java-Themen 3
A Zeilen aus einer Textdatei löschen Allgemeine Java-Themen 6
M Arraylist - Inhalte in Textferldern anzeigen, verändern und löschen. Allgemeine Java-Themen 18
S Liste Object Löschen Allgemeine Java-Themen 7
G Log4J - Logs älter als 3 Tage löschen Allgemeine Java-Themen 5
Quaxli Files massenhaft löschen Allgemeine Java-Themen 3
J Mit POI Zeile in Excel löschen Allgemeine Java-Themen 5
D Kann Tiff Datei nicht löschen Allgemeine Java-Themen 12
0x7F800000 Regex zum löschen vom unnötigen whitespace Allgemeine Java-Themen 4
Daniel_L Best Practice zum Löschen von Log-Files? Allgemeine Java-Themen 8
S Problem beim Löschen des Inhalts des Fensters Allgemeine Java-Themen 4
O Zeile eines Textfiles löschen Allgemeine Java-Themen 2
O File zum löschen "schließen" Allgemeine Java-Themen 2
G JTree Node löschen Allgemeine Java-Themen 2
C String to hex und hex-Werte löschen Allgemeine Java-Themen 2
H Benutzerkonto löschen Allgemeine Java-Themen 4
G Dateien löschen Allgemeine Java-Themen 3
G Datei löschen nach kopieren geht nicht Allgemeine Java-Themen 5
G List- Einträge löschen Allgemeine Java-Themen 3
T probleme mit file löschen Allgemeine Java-Themen 9
F Aus einer XML Datei löschen Allgemeine Java-Themen 3
M Endgültiges Löschen von Objekten Allgemeine Java-Themen 7
H JTable Löschen [Alle Zeilen aufeinmal Löschen] Allgemeine Java-Themen 6
Z Letztes zeichen eines strings löschen Allgemeine Java-Themen 3
S Löschen von Objekt erzwingen Allgemeine Java-Themen 4
T LDAP - Eintrag löschen Allgemeine Java-Themen 6
J Alte Log Files löschen mit log4j Allgemeine Java-Themen 3
C StyledDocument: SimpleAttributeSets löschen? Allgemeine Java-Themen 2
P löschen Allgemeine Java-Themen 5
M JLabels löschen (sollen nicht mehr gezeichnet werden) Allgemeine Java-Themen 10
T Große Dateibestände löschen - Speicherproblem Allgemeine Java-Themen 20

Ähnliche Java Themen

Neue Themen


Oben