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:
und nun die Implementierung des Baums an sich:
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.
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:
Java:
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:
Java:
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.