Baum Knoten löschen

[java_anfänger(=]

Hi Leute,
ich bin ein totaler Java Anfänger und benötige dringend Eure Hilfe

Ich möchte einen Knoten aus einem Baum löschen, aber stehe total auf dem Schlauch...
Mein erstes Problem ist, wie finde ich den Knoten am Besten, also wie muss ich den Baum am Besten durchgehen???
Das Löschen müsste dann ja funktionieren, indem ich den Knoten gleich 0 setze.
Nun meine nächts Frage ist wie verschiebe ich den Baum danach am effektifsten???

Ich weiß, dass wenn man ein Blatt löscht, muss nichts verschoben werden, wenn der Knoten ein Kind setzt ihn durch sein Kind und wenn er zwei Kinder hat, erstetze ihn mit dem größten Knoten im von ihm aus linken Zweig.

Danke für Eure Hilfe

 

[eMmiE]

Wenn du einen Knoten einfach null setzen würdest, würdest du zwar damit die Verbindung lahm legen, aber die unterknoten und Blätter wären theoretisch noch erreichbar.
Die musst du natürlcih auch 0 setzen.

Zu deiner Frage: Ich kann nur helfen, wenn ich ein Code-Beispiel sehe oder so was, sonst ist das alles nur Theorie:rtfm:

Gruß eMmiE

 

[java_anfänger(=]

ahh okay danke
hier ist mein bisheriger Code:

package aufgabe2;

import de.tu.tree.BinNode;


public class BinTreeNode implements BinNode<Integer> {
	
	
	Integer data;
	BinTreeNode left;
	BinTreeNode right;
	
	public BinTreeNode(Integer data) {
		this.data = data;
	}

	public Integer getData() {
		return data;
	}

	public void setData(Integer data) {
		this.data = data;
	}

	public BinTreeNode getLeft() {
		return left;
	}

	public void setLeft(BinTreeNode left) {
		this.left = left;
	}

	public BinTreeNode getRight() {
		return right;
	}

	public void setRight(BinTreeNode right) {
		this.right = right;
	}

	public boolean isLeaf() {
		return right == null && left == null;
	}
	
	public String toString(){
		return data.toString();
	}
	
	
}




package aufgabe2;

import java.util.LinkedList;

import de.tu.tree.Tree;

public class BinarySearchTree implements Tree<Integer> {

	protected BinTreeNode root;
	protected int size = 0;
	private boolean dataAlreadyExisted; 		//Gibt an, ob es den einzufügenden Wert im Baum bereits gibt.

	public BinarySearchTree() {
		this.root = null;
	}

	public BinarySearchTree(BinTreeNode n) {
		root = n;
	}

	public boolean insert(Integer data) {
		
		if (data != null) {						//Kann nur einfügen, wenn auch ein gültiger Wert übergeben wird.
			this.dataAlreadyExisted = false;		//Den Wert gibt es bisher noch nicht.
			this.root = insert(data, this.root);	//Rufe die zweite insert-Methode auf, um den Wert einzufügen.
			
			return this.dataAlreadyExisted;			//Gebe zurück, ob der Wert existiert oder nicht.
		}
		return false;								//Gebe false zurück, falls der Wert null ist.
	}

	private BinTreeNode insert(Integer data, BinTreeNode root) {
		if (root == null) {											//Einfügen in einem Blatt oder wenn der Baum leer ist. Wurzel des Teilbaums ist null, wenn Blatt oder Baum leer.
			this.size++;											//Erhöhe den Wert um 1.
		
			return new BinTreeNode(data);							//Erstelle den neuen Baum.
		
		} else {													//Wir sind noch an keinem Blatt angekommen und suchen weiter!
			if (data.compareTo(root.getData()) < 0) {				//Wir suchen im linken Teilbaum weiter, da der neue Wert kleiner als die Wurzel ist.
				root.setLeft(insert(data, root.getLeft()));			//Rufe rekursiv insert wieder auf für den neuen Teilbaum und setze dann den linken Teilbaum neu!
			
			} else if (data.compareTo(root.getData()) > 0) {		//Wert ist größer als die Wurzel also suchen wir im rechten Teilbaum weiter.
				root.setRight(insert(data, root.getRight()));		  //Rufe rekursive insert wieder auf für den neuen Teilbaum und setze dann den rechten Teilbaum neu.
			
			} else {											//Den Wert gibt es schon im Baum.
				this.dataAlreadyExisted = true;	//Gebe den Baum einfach zurück und setze Boolean auf true.
			}
			return root;
		}
	}

	
	public boolean remove(Integer i) {               // HIER IST MEIN PROBLEM BEREICH!!!
			
			
			return false;
	}

Danke im Vorraus

 

[eMmiE]

Bei dem remove musst du erstmal den Knoten mit dem Wert suchen, wie im insert().
Den Rest hast du eigentlich schon geschrieben:
Wenn er nur Blatt ist, dann setzt du ihn einfach 0.
Das geht meiner Meinung nach so:

Pseudo Code:
if(Knoten.links = wert || Knoten.rechts = wert) {
  if (Knoten.links = wert) {
     if (Knoten.links.isLeaf()) {
       Knoten.links = null;
     } else if (Knoten.unterknotenanzahl < 2) {
       Knoten.links = Knoten.links.getLeft();
     } else {
       //größeren Knoten nehmen
     }
  } else {
  //rechts ebenso
  }
} sonst {
  if (wert < Knoten.links) {
     untersucheKnoten(Knoten.links);
  } else if (wert > Knoten.rechts) {
     untersucheKnoten(Knoten.rechts)
  } else {
     //nicht enthalten
  }
}

 

[java_anfänger(=]

vielen Dank schon mal für deine Hilfe, aber ich stelle mich ziemlich dumm an...
Ich habe es mal probiert, aber ich kriege es nicht hin, dass der den knoten findet(Problem ist markiert), und ich weiß nicht ob der Rest so klappt(letzter Fall ist noch nicht komplett.
Vielen Dank schon mal im Voraus

	public boolean remove(Integer i) {
		
		if(root == null || i == null){
		return false;
		}
		else if(i.compareTo(root.getData()) < 0) {		// Wir suchen im linken Teilbaum, da der Wert kleiner als die Wurzel ist.
			root.left.remove(i);								//PROBLEM!!! suchen im linken Teilbaum
			}
		else if (i.compareTo(root.getData()) > 0) {				// Wert ist größer als die Wurzel also suchen wir im rechten Teilbaum weiter.
			root.setRight(insert(i, root.getRight()));		// Rufe rekursiv insert wieder auf für den neuen Teilbaum und setze dann den rechten Teilbaum neu!
			}	
		if(root.isLeaf()) {								// kein Nachfolger; Fall 1
				root = null; 									// gefundenen Knoten einfach vernichten
				return true;
			}
		else if (root.right.isLeaf() || root.left.isLeaf()){	// Ein Nachfolger; Fall 2
			if (root.right == null){							// Falls der rechte Zweig "leer" ist
				root = root.left;						// Der alte Knoten wird durch den linken Zweig ersetzt 
			}
		else if (root.left == null){						// Falls der linke Zweig "leer" ist
			root = root.right;						// Der alte Knoten wird durch den rechten Zweig ersetzt 	
			}
		else if (root.right != null && root.left != null){	// Zwei Nachfolger; Fall 3
			
		}
			
		}
		
		else
				return false;
				}

 

[eMmiE]

Warum machst du einen Unterschied dabei, ob du links oder rechts weitersuchst?

Wenn remove aufgerufen wird, egal von welchem Knoten, dann musst du zuerst gucken, ob der Knoten den Wert hat

Eingabe: i
if (Knoten.value == i) {
  //hier entfernst du nach den verschiedenen Modi
} else {
  if (Knoten.left < i && Knoten.right > i) {
    return false; //-> nicht vorhanden
  } else {
    if (Knoten.left > i) {
      Knoten.left.remove(i);
    } else {
      Knoten.right.remove(i);
    }
  }
}

Das mit den verschiedenen Modi, bitte ich dich, probier mal bitte selbst:idea:

Gruß eMmiE

 

[lenuyx]

hallo,

vielleicht kann ich ein wenig helfen, ich habe den Stoff gerade auch behandelt und habe auch eine Lösung.

zunächst ein paar Fragen:

handelt es sich um einen binären Suchbaum?
falls ja:
soll der Baum nach dem löschen eines Knotens wieder ein binärer Suchbaum sein?
kennst du die einzelnen Fälle die auftreten können? (Knoten == Kind // Knoten == Wurzel usw.)
falls nein:
bist du sicher das du nur den Wert im Knoten löschen willst? denn ein leerer Knoten ist unschön.

im Anhang befindet sich eine Löschmethode die die "Fälle" umgeht und immer eine Wurzel löscht.
d.h. es wird so lange ein linker/rechter Teilbaum genommen bis der zu löschende Knote in diesem die Wurzel darstellt. Diese wird gelöscht und der Teilbaum wird dem "Mutter"-Baum wieder angehängt.

hoffe ich konnte ein wenig helfen

public void delete(Game e){
		if(!isEmpty()){
			if(root.getValue().compareTo(e) == -1){
				deleteRecursiv(e, getRight(), this);
			}else{
				if(root.getValue().compareTo(e) == 1){
					deleteRecursiv(e, getLeft(), this);
				}else{
					deleteRoot();
				}
			}
		}
	}
	
	private void deleteRecursiv(Game e, Tree n, Tree parent){
		if(!n.isEmpty()){
			if(parent.root.getValue().compareTo(e) == 1){
				if(n.root.getValue().compareTo(e) == 0){
					n.deleteRoot();
					parent.setLeft(n);
				}else{
					if(n.root.getValue().compareTo(e) == 1){
						if(parent.getLeft().root.getValue().compareTo(n.root.getValue()) == 0){
							deleteRecursiv(e, n.getLeft(), parent.getLeft());
						}else{
							deleteRecursiv(e, n.getLeft(), parent.getRight());
						}
					}else{
						if(n.root.getValue().compareTo(e) == -1){
							if(parent.getLeft().root.getValue().compareTo(n.root.getValue()) == 0){
								deleteRecursiv(e, n.getRight(), parent.getLeft());
							}else{
								deleteRecursiv(e, n.getRight(), parent.getRight());
							}
						}
					}
				}
			}else{
				if(n.root.getValue().compareTo(e) == 0){
					n.deleteRoot();
					parent.setRight(n);
				}else{
					if(n.root.getValue().compareTo(e) == 1){
						if(parent.getRight().root.getValue().compareTo(n.root.getValue()) == 0){
							deleteRecursiv(e, n.getLeft(), parent.getRight());
						}else{
							deleteRecursiv(e, n.getLeft(), parent.getLeft());
						}
					}else{
						if(n.root.getValue().compareTo(e) == -1){
							if(parent.getRight().root.getValue().compareTo(n.root.getValue()) == 0){
								deleteRecursiv(e, n.getRight(), parent.getRight());
							}else{
								deleteRecursiv(e, n.getRight(), parent.getLeft());
							}
						}
					}
				}
			}
		}
	}
	
	private void deleteRoot(){
		if(root.getLeft() == null){
			root = root.getRight();
		}else{
			if(root.getRight() == null){
				root = root.getLeft();
			}else{
				Node parent = root.getLeft();
				if(parent.getRight() == null){
					parent.setRight(root.getRight());
					root = parent;
				}else{
					while (parent.getRight().getRight() != null){
						parent = parent.getRight();
					}
					Node temp = parent.getRight();
					parent.setRight(temp.getLeft());
					temp.setLeft(root.getLeft());
					temp.setRight(root.getRight());
					root = temp;
				}
			}
		}
	}

 

[java_anfänger(=]

Danke schon mal an euch beide, iht habt mir geholfen

Ich habe es jetzt so:

public boolean remove(Integer i) {
		
		if(root == null || i == null){
		return false;
		}
		if (root.getData() == i){							// falls der gesuchte Knoten gefunden wurde
			if(root.isLeaf()) {									// kein Nachfolger; Fall 1
				root = null; 									// gefundenen Knoten einfach vernichten
				size--;
				return true;
			}
		else if (root.right.isLeaf() || root.left.isLeaf()){	// Ein Nachfolger; Fall 2
			if (root.right == null){							// Falls der rechte Zweig "leer" ist
				root = root.left;								// Der alte Knoten wird durch den linken Zweig ersetzt 
				size--;
			}
		else if (root.left == null){						// Falls der linke Zweig "leer" ist
			root = root.right;								// Der alte Knoten wird durch den rechten Zweig ersetzt 	
			size--;
		}
		//else if (root.right != null && root.left != null){	// Zwei Nachfolger; Fall  mache ich wenn durchlaufen klappt
		//}
			
		}
		
		else {
		if(i.compareTo(root.getData()) < 0) {				// Wir suchen im linken Teilbaum, da der Wert kleiner als die Wurzel ist.
			root.left.remove(i);							//PROBLEM!!! suchen im linken Teilbaum
			}
		else if (i.compareTo(root.getData()) > 0) {				// Wert ist größer als die Wurzel also suchen wir im rechten Teilbaum weiter.
			root.right.remove(i);								//PROBLEM!!! Rufe rekursiv remove wieder auf für den neuen Teilbaum und setze dann den rechten Teilbaum neu!
			}	
		}
		}
				return false;
		
				}

Mein Problem ist nur, dass die rekursiven Methoden:

root.left.remove(i);

nicht funktionieren, da kommt die Fehlermeldung "the method(remove Integer) is undifined for the type BinTreeNode"
Ohne diese Methode kann ich den Baum nicht durchlaufen, hat jemand eine Idee?

 

[lenuyx]

sehe ich das richtig?

du rufst deine delete Methode mit "baum".remove(int i); auf und dann willst du das root.getleft().remove(int i); auch funktioniert?

ich glaube der fehler liegt darin das du mit root.left einen knoten bekommst und keinen teilbaum oder?

d.h. du führst eine Methode die für bäume gedacht ist auf einen knoten aus.


kleine Zusammenfassung eines bsp. für Funktionen der Klassen Node und Tree:

//class Node:

private Node left;
private Node right;
private int value;

//konstruktor:

public Node (int v,Node l,Node r) {
		value = v;
		left = l; 
		right = r;
	}

//funktionen:

jeweils getter + setter für value,left,right.


//class Tree:

private Node root;

//konstruktor:

public Tree(){
	root = null;
	}

//funktionen:

public Tree getLeft()
public void setLeft(Tree n)
nochmal mit right
public boolean isEmpty()

public void insert(int i)

public boolean delete(int i) // 1 fall + aufruf der rekursiveDelete

private void rekursiveDelete(int i, ****hier müssen noch einige Nodes übergeben werden****) // aufruf deleteNode
private void deleteNode(****hier müssen noch einige Nodes übergeben werden****) // hier wird ein knoten gelöscht 3 fälle berücksichtigt
private void deleteRoot() //1 fall evtl boolean als rückgabetyp

 

[java_anfänger(=]

Okay habs denke ich verstanden und habe es jetzt so(erst mal nur um ein blatt zu löschen):
aber er löscht irgendwie immer den kompletten baum also alles aber warum???
ich verzweifle....

public boolean remove(Integer i) {
		
		this.root = ueberpruefeKinder(i, this.root);
	
		if(root == null){							// falls der knoten null ist oder null gelöscht werden soll
		return false;								// gebe false zurück
		}
		
		else if(root.isLeaf()) {							// kein Nachfolger; Fall 1
			root = null; 									// gefundenen Knoten einfach vernichten
			size--;											// size -1
			return true	;								// gebe true zurück
			}
		
		//else if (root.right.isLeaf() || root.left.isLeaf()){	// Ein Nachfolger; Fall 2
			//if (root.right == null){							// Falls der rechte Zweig "leer" ist
				//root = root.getLeft();							// Problem!!! er soll den ganzen teilbaum ra n hänegn und nicht nur den nächtsen knoten!! //Der alte Knoten wird durch den linken Zweig ersetzt 
				//size--;											// size - 1
			//}
		//else if (root.left == null){						// Falls der linke Zweig "leer" ist
			//root = root.getRight();							// Problem!!! er soll den ganzen teilbaum ra n hänegn und nicht nur den nächtsen knoten!!// Der alte Knoten wird durch den rechten Zweig ersetzt 	
			//size--;											// size - 1
		//}
		//else if (root.right != null && root.left != null){	// Zwei Nachfolger; Fall 3	
			
			//	root = root.left;							// Knoten ist gleich der oberste Knoten seines linken teilbaumes
				//if (root.right == null){					// wenn der knoten keinen rechten teilbaum hat 
					
				//}
					//i.compareTo(root.getData()
			
		//}
			
		//}
		//}
				return false;
		
		
				}
	
	public BinTreeNode ueberpruefeKinder(Integer i, BinTreeNode root){
		if(root.getData() == null || i == null){
			return null;
		}
		else if (root.getData() == i){
			return root;	 
			}
		else if(i.compareTo(root.getData()) < 0){
			return ueberpruefeKinder(i, root.left);
		}
		else if (i.compareTo(root.getData()) > 0) {
			return ueberpruefeKinder(i, root.right);
		}
		
		return root;
	}

 

[lenuyx]

könntest du evtl. alle deine Klassen zu dem Projekt hochladen? ich würde das ganze mal bei mir aufspielen und testen. (bitte nicht als Java code hier im Forum da ich via copy/paste keine zeilenumbrüche habe)

wir könnten uns auch direkt via Skype oder TS unterhalten wenn du magst.