Hilfe ... Suchbaum ...Löschen

[Lotsche]

Hallo liebes Forum,

ich habe die Aufgabe ein Java-Programm für einen Suchbaum zu schreiben. Insbesondere zum Löschen von Knoten habe ich noch Probleme und Fragen. Ich hoffe auf eure Hilfe!

Hier ist der Java-Code, den ich bis jetzt habe:

zunächst die Knoten des Baums:

class TreeNode<KeyType extends Comparable<KeyType>, DataType>{
    
    public KeyType key;
    public DataType data;
    public TreeNode<KeyType,DataType> parent;
    public TreeNode<KeyType,DataType> left;
    public TreeNode<KeyType,DataType> right;
    public TreeNode(KeyType k, DataType d) {
            key = k; data = d; left = right = parent = null;
    }
}

und nun die Implementierung des Baums an sich:

public class SearchTree<KeyType extends Comparable<KeyType>, DataType>{
    
    //sucht nach Knoten
    public TreeNode<KeyType, DataType> search (KeyType k) {
        TreeNode<KeyType, DataType> currentNode = root;
        while (currentNode != null){
            if (k.compareTo(currentNode.key)== 0) return currentNode;
            if (k.compareTo(currentNode.key) < 0)
                currentNode = currentNode.left;
            else
                currentNode = currentNode.right;
        }
        return null;
    }
    
    
    //schaut, ob Knoten enthalten ist
    public DataType isMember (KeyType k) { 
        TreeNode<KeyType,DataType> node = search( k );
        if ( node == null ) return null;
        return node.data;
    }
    
    //fuegt in Knoten ein
    public boolean insert(DataType d, KeyType k) { 
        TreeNode<KeyType, DataType> node =new TreeNode<KeyType,DataType>(k,d);
        if (root==null){
            root = node; 
            return true;
        }
        TreeNode<KeyType, DataType> currentNode = root;
        TreeNode<KeyType, DataType> parentNode = null;
        while (currentNode != null){
            parentNode = currentNode;
            if (k.compareTo(currentNode.key) == 0) return false;
            if (k.compareTo(currentNode.key) < 0)
            currentNode = currentNode.left;
            else
                currentNode = currentNode.right; 
        }
        node.parent = parentNode;
        if (k.compareTo(parentNode.key) > 0)
            parentNode.right = node;
        else
            parentNode.left = node;
        return true;
    }
    
 
    //loescht Knoten
    @SuppressWarnings("null")
    public boolean remove(KeyType k) {
        TreeNode<KeyType, DataType> node = search( k );
        
        TreeNode<KeyType, DataType> ersatz = null;
        
        //Falls zu loeschender Knoten keine Kinder hat
        if(node.left==null && node.right==null)
        {
            node=null;
            node.left=null;
            node.right=null;
        }
        
        //Falls zu loeschender Knoten nur ein Kind besitzt (links)
        else if(node.left!=null && node.right==null)
        {
        node.parent=node.left;
        node.right=null;
        node.data=null;
        }
        
        //Falls zu loeschender Knoten nur ein Kind besitzt (rechts)
        else if(node.left==null && node.right!=null)
        {
        node.parent=node.right;
        node.left=null;
        node.data=null;
        }
        
        //Falls zu loeschender Knoten zwei Kinder besitzt 
        else
        {
            ersatz=findMax(node.left);
            node.data=ersatz.data;
            node=ersatz;
            ersatz=ersatz.left;
        }
        
        node.data=ersatz.data;
        node.left=ersatz.left;
        node.right=ersatz.right;
        
        return true;
    
    }
    
    //liefert groessten Wert im Teilbaum
    public TreeNode<KeyType, DataType> findMax (TreeNode<KeyType, DataType> t) {
        
        while (t.right != null){
            t=t.right;
        }
        return t;
    }
    

public SearchTree() {
root = null;
}
private TreeNode<KeyType, DataType> root;
public TreeNode<KeyType, DataType> getRoot() {
return root;
}
 
}

Es geht hauptsächlich um die Löschfunktion, da die anderen Funktionen bereits behandelt wurden sind. Mir sind alle drei Fälle (+ Sonderfall, dass die Wurzel gelöscht werden soll) an sich klar. Wenn der Knoten keine Kinder hat, muss der Knoten einfach auf null gesetzt werden. Muss hier der Keytype und der Datatype direkt angesprochen werden oder genügt es node=null zu setzen?
Falls der Knoten ein Kind hat, muss der Vater des zu löschenden Knotens auf das rechte bzw. linke Kind zeigen. Der dritte Fall ist für mich der schwierigste. Ich hab in vielen Beispielen im Netz gelesen, dass ich in dem Teilbaum, des zu löschenden Knotens das Maximum finden muss, damit ich dieses ersetzen kann. Jedoch ist mir der direkte Ablauf nicht ganz klar. Ich hoffe, dass mein eigener Versuch nicht allzu falsch ist.
Der letzte Fall, in welchem die Wurzel gelöscht werden soll, würde ich so lange alle Kinder löschen, bis ich den Data-Wert null der Kinder erreicht habe. Ist das so korrekt?

Bzw. wenn man die Wurzel löschen will, will man ja quasi den kompletten Suchbaum löschen. Kann man da eigentlich jedes mal die Wurzel löschen und die Kinder der eigentlichen Wurzel als neue Wurzeln setzen und wieder und wieder löschen? Man würde ja mehr als eine Wurzel bei getRoot() zurückbekommen.


Würde mich über Antworten sehr freuen.

 

[Cymatoxa]

Hi,

ich verstehe deinen Code ehrlich gesagt nicht zu 100%. Das ist jetzt aber auch nicht so wichtig, wird schon passen, hab ihn auch nur überflogen. Das Prinzip beim Löschen (Left/right ist die relative Position des zu löschenden Elements zu seinem Parent):
Node hat höchstens ein Child:
parent.left/right = child
Damit geht der Verweis auf das Element verloren, an dessen Stelle kommt sein Child-Element. Methode funktioniert auch, wenn das zu löschende Element kein Child hat, denn dann gilt ja parent.left/right = null.
Node hat zwei Children:
parent.right/left = leftChild
unterstes rechtes element in leftChild .right = rightChild
Also du setzt einfach die linke Seite an das Parent-Element, die rechte seite ganz rechts unten an das gerade angesetzte. (Du gehts also die children nacheinander durch: node=node.right, solange node.right != null ist. An das setzt du an der rechten seite die alte rechte Seite des geslöschten Elements.)
Uff... ist eigendlich ganz einfach, hört sich aber so formuliert ziemlich seltsam an :/
Schau einfach mal hier: http://de.wikipedia.org/wiki/Binärbaum#L.C3.B6schen

Zu deiner anderen Frage: Nein, wenn du einen Knoten löscht, sollen dessen Child-Elemente nicht mitgelöscht werden. Wenn du also root löscht, wird einer seiner Children zum neuen root.

Viel Erfolg,

Cymatoxa