Java Suchbaum - Knoten löschen

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:

Code:

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:

Code:

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.

 

auch wenn ich meine java lektionen erfolgreich verdrängt habe...

du greifst nie auf den parent knoten zu, um dort irgend einen zeiger umzubiegen. das halte ich so für nicht ganz korrekt.

 

Zuerst ein paar fragen .. Warum sind deine Funktionen alle boolean ? Ist es dir wichtig einen Wahrheitswert zu erhalten ? Sonst würde ich schon mit void arbeiten damit ebend keine unnötigen Rückgabe werte kommen. Statt @SuppressWarnings vll ein paar if abfragen ob Note = null oder ein Zeiger null. Ist nur schöner klappt natürlich auch so. Okay dann Fall 1. Keine Kinder . Node = null kannst du dir sparen und ich bin mir eig sicher,dass das eh nichts tut. Bei Java ist es so, dass Objekte auf die du nichtmehr zugreifen kannst, gelöscht sind. Also reicht es vom Parent den Verweis auf null zu setzen. Also zbb wenn du den untersten rechten Knoten löschen möchtest,gehst du einen Schritt wieder hoch und setzt die Zeiger (vom Parent zum Child und Child zum Parent) auf null. Damit gibt es keinen Zeiger mehr auf den zu löschendes Element und es verschwindet.
Fall 2. einen Nachfolger: Du nimmst den Zeiger des Parents und setzt diesen eine Ebene tiefer auf den Nachfolger des zu löschenden Knotens. Und entfernst die Zeiger des zu löschenden zum parent und zum child. So hat es wieder keinen Zeiger auf sich und gilt als gelöscht.

Fall 3: (Das betrifft auch das Löschen der Wurzel) Du suchst das kleinste Größere Element und tauscht dieses mit deinem zu löschenden, indem du wieder alle Zeiger umbiegst wie sie sollen.

Die Wurzel löschen ist mit Fall 3 identisch.
Der Ablauf wäre etwa so, du gehst zur Wurzel die zu löschen ist .. gehst in den rechten Teilbaum (weil dort größere) und dort nach links unten ( das kleinste größere Element sitzt dort ) Analog ginge auch linker Teilbaum ,rechtester Knoten. Ist das so verständlicher ?

Kazhar hat übrigens nicht Recht Binäre Suchbäume wie du sie hast können beidseitig verkettet sein und in allen Fällen muss eine Beziehung zum Parent erhalten sein zum löschen bzw einfügen.


if(node.left==null && node.right==null) // Wenn node.left == null ...
{
node=null;
node.left=null; // Dann node.left= null ? Das ist unsinn.. node.parent.left=null;
node.right=null;
}