binärer suchbaum

[ETlearner]

hallo,
habe wieder mal aufgaben zu erledigen -.-
die aufgabe lautet:
Implementieren Sie einen Datentyp SearchTree<T>, der einen Suchbaum mit Elementen
des generischen Typs T reprasentiert. SearchTree<T> soll die folgenden Eigenschaften
besitzen:
Der Suchbaum entspricht den Spezikationen:
1. Datenobjekte werden nur in den Blattern gespeichert.
2. Interne Knoten eines Suchbaums besitzen genau zwei Nachfolger.
3. Elemente im linken Teilbaum eines Knotens x sind stets kleiner oder gleich dem
Element von x.
4. Elemente im rechten Teilbaum eines Knotens x sind stets grosser als das Element
von x.
{ Es gibt eine Methode public void insert(int key, T element), die ein neues
Element in den Suchbaum einordnet.
dannach soll ich no eine delete-methode implementieren, welches ein element löscht und eine methode tostring, die alle values der blätter auf der konsole ausgibt. aber soweit bin ich leider noch nicht.

dieser quellcode war schon im tutorium gegeben:

class BinarySearchTree<T>{
	abstract class Node{
		int key;
		//Konstruktor
		public Node (int key){
		this.key = key;
		}
		public abstract T search(int key); // wird selbst nie aufgerufen, immer ein Objekt vom Typ Fork oder Leaf, die ihre jeweiligen Methoden anwenden
	}

	class Fork extends Node{
		Node leftChild;
		Node rightChild;
		//Konstruktor
		public Fork(int key, Node lc, Node rc){		// Fork ist ein innerer Knoten
		super(key);
		this.leftChild = lc;
		this.rightChild = rc;
	}
		public T search(int key){					
			if (this.key <= key) {
			return rightChild.search(key);
			}
			else { // kleiner gleich immer links lang
			return leftChild.search(key);
			}
		}
	}

	class Leaf extends Node{
		T value;
		//Konstruktor
		public Leaf(int key, T val){
		super(key);
		this.value = val;
		}
		public T search (int key){
		if (this.key == key){
		return this.value;
		}
		else {
		return null;
		}
		}
	}
	
	
	private Node root;
	//Konstruktor
	public BinarySearchTree(){
	this.root = null;
	}

ich habe versucht, die insertmethode zu implementieren...

	public void insert(int key, T value){
		Node a=root;
		if (root==null){ 
			root=new Leaf(key,value);
		}
		else if(a instanceof Leaf){
			if(key<=a.key){
				root=new Fork(key, new Leaf(key,value), new Leaf(a.key, a.value));
				}
			else{ root=new Fork(a.key,  new Leaf(a.key, a.value), new Leaf(key,value));
			}	
		}
		else{ 
			Node b=a.search(key);
			if(key<=b.key){
				root=new Fork(key, new Leaf(key,value), new Leaf(b.key, b.value));
				}
			else{ root=new Fork(b.key,  new Leaf(b.key, b.value), new Leaf(key,value));
			}
		}
				
	}

ich habe die 3 fälle unterschiede:
baum leer--> wurzel root ist dann übergebener wert
wurzel ist ein Blatt--> vergleichen der schlüssel--> root wird Fork und erhält zwei kindknoten vom typ Leaf

bei der dritten fallunterscheidung komme ich leider nicht so richtig weiter... und ich erhalte fehlermeldungen, die ich nicht beseitigen kann

wäre sehr dankbar, wenn ich paar tipps erhalte, wie ich besser vorgehen könnte, da ich immer durcheinanderkomme

lg

 

[SlaterB]

der erste Tipp ist immer der gleiche:
vergiss Java, schau dir auf dem Papier an was passieren muss,
hast du vielleicht, im Grunde steht es durch die Regeln ja auch schon da,

aber nimm dir ein bestimmtest Beispiel vor, welches du dann auch durch eine main-Methode abbildest und hier postest,
welche Werte willst du in welcher Reihenfolge einfügen? wie genau sieht der Baum jeweils vorher und nachher aus,
was davon leistet dein Code schon (etwa das erste Einfügen?), wo scheitert es und auf welche Weise,
was stellst du das fest oder sagst du dir einfach dass du deinen Code lieber gar nicht erst laufen lässt?

was passiert auf dem Papier genau bei einem bestimmten kritischen Schritt? welche Elemente sind alle neu dabei,
wo gibt es Zeiger/ Links, welche ändern sich zum vorherigen Zustand, hast du schon einen Plan das in Code abzubilden usw.

du kannst locker 3 Seiten und noch mehr schreiben, alles tausendfach im Detail erklären, dabei selber vielleicht lernen,
oder eben nur einen Code schreiben und andere korrigieren lassen?
in Suchmaschinen findest du übrigens sicher beliebig viele fertige Implementierungen

ein Tipp: abgesehen vom ersten if kommt root nur noch begrenzt vor,
durchaus wenn ein neuer Zwischenknoten den vorherigen root ersetzt, aber nicht viermal als ganz normale Anweisung wie in deinem Code

 

[ETlearner]

ich versuche es jetzt dann mal auf diese weise zu machen

 

[ETlearner]

habe durch simulationen versucht den quellcode richtig zu implementieren-.- :

public void insert(int key, T value){
		Node a=root;
		if(root==null){
			root=new Leaf(key, value);
		}
		
		else if(a instanceof Fork){
			if(key <= a.key){
				Node left= new Leaf(key,value);
				Node right= new Leaf(a.key,a.value);
				root= new Fork(key, left, right);
			}
			else{
				Node right= new Leaf(key,value);
				Node left= new Leaf(a.key,a.value);
				root= new Fork(a.key, left, right);
			}
		}
		
		else{
			a=a.search(key);
			if(key <= a.key){
				Node left= new Leaf(key,value);
				Node right= new Leaf(a.key,a.value);
				root= new Fork(key, left, right);
			}
			else{
				Node right= new Leaf(key,value);
				Node left= new Leaf(a.key,a.value);
				root= new Fork(a.key, left, right);
			}

			
		}	
}

leider erhalte ich 6 fehlermeldungen die ich nicht beseitigen kann...
geht die implementierung in die richtige richtung oder ist es wieder mal blödsinn -.-

 

[SlaterB]

du verzichtest weiter auf jede Zeile Erklärung,

ich kann erkennen dass du weiter root immer überschreibst, den einzigen Punkt den ich angesprochen hatte,
zudem sind die neuen Node-Zeilen eigentlich nur ausgeschriebene Varianten des vorherigen, als du sie jeweils direkt übergeben hattest
([c]root=new Fork(key, new Leaf(key,value), new Leaf(a.key, a.value));[/c])

ich lasse ja mit mir reden, aber das ist bisschen sehr dürftig an Fortschritt

 

[ETlearner]

public void insert(int key, T value){
		Node a=root;
		if(root==null){				//bei einem leeren baum setze root als neuen Blatt mit dem jeweiligen schlüssel und wert
			root=new Leaf(key, value);
		}
		
		else if(a instanceof Fork){ // ist root eine instanz von Blatt,so vergleiche key mit dem key von a
			if(key <= a.key){		// wenn key <=a.key, so
				Node left= new Leaf(key,value);	//ist das linke kind ein blatt mit dem schlüssel key und dem wert value und
				Node right= new Leaf(a.key,a.value); // das rechte kind ein blatt mit den eigenschaften von a
				root= new Fork(key, left, right);	// mithilfe des konstruktors werden die kinder an dan elternknoten gebunden
			}
			else{
				Node right= new Leaf(key,value);	// analog
				Node left= new Leaf(a.key,a.value);
				root= new Fork(a.key, left, right);
			}
		}

		
		else{
			a=a.search(key);		// diese zeile ist merke ich grad iwie unlogisch (***)
			if(key <= a.key){		// wenn man an einem blatt angekommen ist, führt man analog zur obigen elseif-implementierung die operationen durch
				Node left= new Leaf(key,value);
				Node right= new Leaf(a.key,a.value);
				a= new Fork(key, left, right);
			}
			else{
				Node right= new Leaf(key,value);
				Node left= new Leaf(a.key,a.value);
				a= new Fork(a.key, left, right);
			}
			
		}
			
			
}

bei (****): kann ich überhaupt das richtige blatt mithilfe der searchmethode finden oder ist die searchmethode dafür nicht geeignet?
und ist die implementierung völlig verkehrt??? root soll ja bei den fällen, dass der baum leer ist oder nur ein element hat verändert werden... oder nicht?

 

[SlaterB]

du dockterst im Code herum ohne auf das Papier zu schauen,
wenn root leer ist dann ist gut und dann schreibe auch return zum Abbruch um danach nicht zig Zeilen in else schreiben zu müssen,

die erste Aufgabe danach ist das search(),
genau wie du auf Papiert in einem großen Baum mit 5 Ebenen erstmal suchen musst, wo der neue Wert hingehört,

wenn du damit das a bestimmt hast, mag ein Block

if(key <= a.key){       // wenn key <=a.key, so
                Node left= new Leaf(key,value); //ist das linke kind ein blatt mit dem schlüssel key und dem wert value und
                Node right= new Leaf(a.key,a.value); // das rechte kind ein blatt mit den eigenschaften von a
                root= new Fork(key, left, right);   // mithilfe des konstruktors werden die kinder an dan elternknoten gebunden
            }
            else{
                Node right= new Leaf(key,value);    // analog
                Node left= new Leaf(a.key,a.value);
                root= new Fork(a.key, left, right);
            }

als Grundstruktur genügen, mit root hat das aber nicht unbedingt zu tun wenn du annehmen musst,
dass du dich auf 12 Ebenen tiefer befinden kannst,
speichere den neuen Fork erstmal in einer lokalen Variable,

du musst den nächsthöheren Knoten finden und dort den passenden Nachfolge-Link neu setzen,
vielleicht läßt du auch lieber den vorhandenen Knoten bestehen und änderst den Inhalt, so dass das bisherige a zum Fork wird,
na gut, das geht wohl nicht, ein Leaf kann kein Fork werden, obwohl sogar der key gleichbleiben würde..,

je nach dem ob es keinen nächsthöheren Knoten gibt, kann auch wieder root betroffen sein, da verrate ich nun aber ne Menge,
testet du überhaupt? einen Baum als Beispiel bestimmt auch noch nicht gemalt..

die search()-Methode achtet übrigens überhaupt nicht ob irgendwann mal null kommt, das kann ja kein gutes Ende geben,
eine Rekursion ohne Abbruchbedingung ist immer falsch

 

[ETlearner]

if(key <= a.key){       // wenn key <=a.key, so
                Node left= new Leaf(key,value); //ist das linke kind ein blatt mit dem schlüssel key und dem wert value und
                Node right= new Leaf(a.key,a.value); // das rechte kind ein blatt mit den eigenschaften von a
                root= new Fork(key, left, right);   // mithilfe des konstruktors werden die kinder an dan elternknoten gebunden
            }
            else{
                Node right= new Leaf(key,value);    // analog
                Node left= new Leaf(a.key,a.value);
                root= new Fork(a.key, left, right);
            }

als Grundstruktur genügen, mit root hat das aber nicht unbedingt zu tun wenn du annehmen musst,
dass du dich auf 12 Ebenen tiefer befinden kannst,
speichere den neuen Fork erstmal in einer lokalen Variable,

aber in diesem fall soll ja root verändert werden... dieser fall tritt ein, wenn root ein blatt ist. also gibt es keine kinderknoten-> root wird zu einem fork und erhält zwei kinder , die aus der klasse leaf instanziiert wurden

 

[SlaterB]

wenn du meinst das erkennen zu können, dann bitte,
ich bin mir im Moment gar nicht mehr sicher was deine search-Methode liefert,
überlege doch wirklich was passieren soll wenn etwa der zweite Knoten eingefügt wird,

es muss doch feste Regeln geben nach denen du entscheidest, diese auch umsetzen,
ich verlange jetzt wirklich erst die Regeln, vorher ist doch der Code egal

dass root ein Fork ist wird wohl nicht reichen, wenn root kein Leaf ist, was vielleicht ein interessanter Fall ist, den du vielleicht sogar meinst, wird root immer ein Fork sein