Altklausur Aufgabe 4, 25.02.2010
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Suchbäume
Hey,
ich hab ne Frage zu folgender Aufgabe:
Gegeben sei folgende Datenstruktur für einen binären Suchbaum. Sie können annehmen,
dass jeder Wert (value) nur maximal einmal im aktuellen Suchbaum abgelegt wurde,
mindestens ein Wert größer und mindestens ein Wert kleiner als die Wurzel ist. Der
leere Baum wird mit null repräsentiert.
class BinTree{
public BinTree left, right;
public int value ;
public BinTree(int v){
value = v;
}
}Implementieren Sie die Methode getNext(), die beim Aufruf für einen Knoten r des
Suchbaums mitWert r.value den nächst-größeren, im Baum gespeichertenWert liefert.
Sie können zur Vereinfachung davon ausgehen, dass es einen solchen Wert gibt.
Und zwar bin ich mir uneinig was für variablen usw. ich schon habe und welche nicht.
Meine Idee war folgendes:
static int getNext(BinTree r) {
int result;
if(r.right!=null){
r=r.right;
while(r.left!=null){
r=r.left;
}
result=r;
else if(r.right=null){
result r.parent;
}
return result;
}Ich kann doch nicht so richtig programmieren, aber naja.
Sie können zur Vereinfachung davon ausgehen, dass es einen solchen Wert gibt.
daher mMn ohne die "if"s und result den wert zuweisen und nicht den BinTree:
static int getNext(BinTree r) {
int result;
r = r.right;
while(r.left != null){
r=r.left;
}
result = r.value;
return result;
}
1 „Gefällt mir“
was mir aber nicht klar wird wieso betrachtet man nicht den fall wenn r ein Blatt ist?
In der Aufgabenstellung steht doch nur, dass man davon ausgehen kann dass es einen größeren wert gibt?
__
und wieso kann man einfach r.value sagen, woher weiß das programm, dann um welchen Knoten es sich handelt ?
in der Aufgabenstellung steht noch mehr:
Implementieren Sie die Methode getNext(), die beim Aufruf für einen Knoten r des
r zeigt doch in dieser zeile schon auf den knoten mit dem nächst größerem wert, dank der 2 vorherigen zeilen.
und value ist ein in der aufgabenstellung deklariertes attribut.
also langsam komm ich mir leicht dämlich vor.
In der Aufgabenstelllung steht:
“Implementieren Sie die Methode getNext(), die beim Aufruf für einen Knoten r des
Suchbaums mitWert r.value den nächst-gr¨oßeren, im Baum gespeichertenWert liefert.
Sie k¨onnen zur Vereinfachung davon ausgehen, dass es einen solchen Wert gibt.”
Woher entnimmst du jetzt dass ich den Fall, dass der Knoten r ein Blatt ist, weglassen kann?
Es gibt kein Attribut parent des BinTrees, d.h. du kannst gar nicht im Suchbaum zurück laufen, und selbst wenn du es könntest und der Knoten, den du übergeben bekommst ein Blatt ist, ist noch lange nicht gesagt, dass der Vaterknoten dann einen größeren Wert hat:
Folgendes Beispiel:
[m]
10
/
8
/
7 9
[/m]
und du bekommst 9 übergeben. Dann müsstest du zwei mal nach oben laufen, um den nächstgrößeren Wert zu finden.
Ich glaube mit “mindestens ein Wert größer und mindestens ein Wert kleiner als die Wurzel” ist die Wurzel gemeint, die du übergeben bekommst.
hier stand unsinn
aber ein knoten ist der überbegriff für ein Blatt und eine Wurzel. Das sind alles gleichzeitig ja auch Knoten.
danke neverpanic!
Jetzt ergibt es sinn.
Ich find es irgendwie schade, dass in jeder 2. Klausuraufgabe die Aufgabenstellung missverständlich gestellt ist. Da ist man ja in der Klausur erst recht verwirrt.
Hey Leutem
ich hab ne Frage zu der Implementierung des Löschvorgangs aus einem binären Suchbaum.
Und zwar geht es mir um den in der Vorlesung verwendetetn Code auf Folie 13-31/32
Es geht um den komischen Sonderfall am Ende. Ich hab mir jetzt auch schon die VL-Aufzeichnungen angeschaut aber da erklärt der Prof Brinda leider nicht den Sonderfall und mir wird der irgendwie nicht ganz klar.
Mir geht es speziell um dieses Stück:
if (right.value == null) {
right = right.right;
if (right != null) right.parent = this;Die Methode removeMin wird hier für einen Teilbaum aufgerufen und kennt dann auch nur diesen Teilbaum.
Problem ist, dass die Wurzel jetzt das zu löschende Minimum von dem Baum ist (und somit innerhalb der Methode keinen Vater hat)
Normalerweise würden wir jetzt um diesen Knoten zu löschen sagen:
Setze den Wert des zu löschenden Knoten auf null.
Der Vater vom rechten Kind ist jetzt nichtmehr der zu löschende Knoten, sondern dessen Vater.
Und hier liegt das Problem. Die Methode weiß nicht, wer der Vater vom zu löschenden Knoten ist (weil der zu löschende Knoten ja die Wurzel von dem Baum ist, den die Methode übergeben bekommt)
Für alle anderen Knoten funktioniert das, weil die auch innerhalb dieser Methode Väter haben.
In deinem Codestück wurde die Methode removeMin wieder verlassen und der komplette Baum ist bekannt.
Erst hier kann das mit dem Umbiegen der Väter also gemacht werden.
Hoffe das war halbwegs verständlich
Stimmt die Methode insert?
static boolean insert ( BinTree b, int value) {
while(true) {
if(value == b.value)
return false;
else if( value < b.value) {
b = b.left;
if(b == null) {
b = new BinTree(value);
return true;
}
} else {
b = b.right;
if(b == null){
b = new BinTree(value);
return true;
}
}
}
}
Nein, da du zwar wenn ich das recht sehe die passende Stelle zum einfügen suchst, dann aber wenn du angekommen bist keine Möglichkeit hast deinen neuen Blattknoten einzufügen, da du dir den Vorgänger nicht gemerkt hast.
Nur b zu setzen reicht hier nicht, da b ja nur eine lokale Variable in der Funktion ist.
Btw: Du tust dir und dem Korrektor einen Gefallen wenn du das rekursiv anstatt iterativ umsetzt, ein guter Compiler macht eh wieder iterativen Code draus. (nein javac nicht)
1 „Gefällt mir“
static boolean insert ( BinTree b, int value) {
//nachfolger
BinTree next = b;
if(value == b.value)
return false;
else if( value < b.value) {
next = b.left;
if(next == null) {
b.left = new BinTree(value);
return true;
} else
return insert(next,value);
} else {
next = b.right;
if(next == null){
b.right = new BinTree(value);
return true;
} else
return insert(next,value);
}
}Fehler gesehn ja, und gleich rekursiv… jetz müssts passen oder?
1 „Gefällt mir“
Sieht ganz gut aus, du könntest dir noch eine Spur Schreibarbeit sparen wenn du die Zeile
einfach ans Ende schreibst, dann brauchst du sie nämlich nur einmal. 