P4 - Step 4

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: P4 - Step 4

Beitrag von zimpfer »

tanne hat geschrieben:wie steigst du rekursiv links und rechts ab ? mit welchen bedingungen ?
Genauso wie bei add...
Wenn vom gesuchtem Knoten interval.start kleiner ist als der aktuelle Knoten oder das Interval.start gleich und der agent kleiner ist nehme ich den linken Teilbaum, ansonsten den rechten

EDIT: ...

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: P4 - Step 4

Beitrag von zimpfer »

Nun hab ich doch einen Fehler im removeSmallest, ich komme einfach nicht drauf, wie ich die Rekursion genau mache.

Hab mir überlegt, dass ich mit Hilfe von node.left=removeSmallest(node.left).node erstmal den Restgraph berechne (bis node.left=null),

Aber dann hab ich das Problem, wie ich den gelöschten Knoten mit in die Ausgabe reinbekomme...


Wie habt ihr das rekursiv aufgerufen?

VMann
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 16. Apr 2009 11:51

Re: P4 - Step 4

Beitrag von VMann »

Mein removeSmallest geht erstmal soweit in die Rekursion wie nötig.
Wenn es da wieder rauskommt übernimmt es einfach den gelöschten Knoten aus der tieferen Rekursion in das eigene RemoveResult und fügt den übriggebliebenen Teilbaum zusammen.
Computer tun nicht das, was du von ihnen willst, sie tun das, was du ihnen sagst.

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: P4 - Step 4

Beitrag von daniel_b »

Ich hab die Schnauze echt langsam voll. Alles fertig, nur der #4-randomTest meint (neuerdings) "Tree is in sorted order". Hat da schon jemand Erfahrungen mit?

// Genaugenommen scheitern alle Tests, die in random() aus diesem check() da aufgerufen werden. Also Sortierung, Höhe, Biggest.. etc. etc.
Ich weiss gerade echt nich weiter.

tanne
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 30. Sep 2008 16:05

Re: P4 - Step 4

Beitrag von tanne »

daniel_b hat geschrieben:Ich hab die Schnauze echt langsam voll. Alles fertig, nur der #4-randomTest meint (neuerdings) "Tree is in sorted order". Hat da schon jemand Erfahrungen mit?

// Genaugenommen scheitern alle Tests, die in random() aus diesem check() da aufgerufen werden. Also Sortierung, Höhe, Biggest.. etc. etc.
Ich weiss gerade echt nich weiter.
das klingt als würdest du den baum nach der rekursion wieder falsch zusammen setzen... wie sind denn deine aufrufe in der rekursion und deine zuweisung dabei un im anker ?

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: P4 - Step 4

Beitrag von daniel_b »

Puh, welche Rekursion meinst du denn genau?

Ich hab jetzt gemerkt, dass die Probleme (nur?) auftreten, wenn ich die absolute Wurzel löschen will. Bei allen anderen Knoten (auch "Sub-Wurzeln" mit linken/rechten Unterbäuen) läuft alles wie geschmiert. Kann ich gerade echt nicht nachvollziehen wo der Unterschied zwischen diesen Fällen besteht.

tanne
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 30. Sep 2008 16:05

Re: P4 - Step 4

Beitrag von tanne »

der "unterschied" ist , dass man bei der absoluten wurzel bei nem größeren baum viel tiefer gehn muss un viel mehr balancieren muss....eine "subwurzel" kann richtig gelöscht werden obwohl der code nich 100% richtig ist, aber bei der absoluten wurzel kann eben dieser fehler auftauchen ...

ich meine die rekursion von removeSmallest....
und setzt du in der remove funktion wenn du removesmallest aufgerufen hast den baum wieder richtig zusammen ? vorallem den linken teilbaum?

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: P4 - Step 4

Beitrag von daniel_b »

Halt mal. Ist das hier korrekt? Mit Augenmerk auf den rechten Teilbaum.. (Balance is gegeben)

Code: Alles auswählen

        4
    /         \
   ...          6
               /   \
               5   7
6 löschen!

Code: Alles auswählen

        4
    /         \
  ...          7
               /  
               5  
Muss es unbedingt 5(rechts)7 heißen oder is mein 7(links)5 hier auch okay? Evtl. passt dem Test mein smallest nicht... wobei der resultierende Baum trotzdem stimmt.

tanne
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 30. Sep 2008 16:05

Re: P4 - Step 4

Beitrag von tanne »

nein das sitmmt so nicht....da du ja nicht den kleinsten wert nimmst, das müsste die 5 sein

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: P4 - Step 4

Beitrag von daniel_b »

//blubb.. siehe unten
Zuletzt geändert von daniel_b am 17. Jun 2009 13:02, insgesamt 3-mal geändert.

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: P4 - Step 4

Beitrag von daniel_b »

// edit: problem gelöst! läuft! :D

ich hab tatsächlich zu viel nach rechts geschaut und zusätzlich noch ein updateBiggest() vergessen

dankeschön! jetzt muss ich nur noch unter 100 sek kommen...

Benutzeravatar
Mark_G
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 8. Okt 2008 23:07

Re: P4 - Step 4

Beitrag von Mark_G »

Arrh... ich hab jetzt remove() und removeSmallest() neugeschrieben, sodass sie rekursiv laufen und jetzt sieht es deutlich übersichtlicher aus und es funktioniert alles... bis auf den Remove-RandomTest! Der quittiert nämlich mit einer nullpointerexception... und die kommt dadurch zustande, dass ich den vierten zu löschenden Knoten nicht mehr im Baum finde! :shock:

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: P4 - Step 4

Beitrag von linn »

Ich krieg beim randomtest auch immer nen stackoverflowerror wenn ich die removeSmallest rekursiv mach...
dabei mach ich eigentlich if(node.left != null) {removeSmallest(node.left)}, sollte also eigentlich nicht so tief in die rekursion gehen...
was mich auch wundert: der stackOverflowError wird von der size() funktion im testcase ausgelöst oO

Benutzeravatar
leviathan
Computerversteher
Computerversteher
Beiträge: 307
Registriert: 30. Jul 2008 14:26
Wohnort: Darmstadt
Kontaktdaten:

Re: P4 - Step 4

Beitrag von leviathan »

linn hat geschrieben:was mich auch wundert: der stackOverflowError wird von der size() funktion im testcase ausgelöst oO
Wovon der Overflow letztendlich kommt, ist unwichtig. Dass er kommt, ist ein (relativ) eindeutiger Hinweis auf eine Endlosscheife im Code.
linn hat geschrieben:dabei mach ich eigentlich if(node.left != null) {removeSmallest(node.left)}, sollte also eigentlich nicht so tief in die rekursion gehen...
Du machst das aber nur so lange, bis er an dem eigentlich zu löschenden Knoten ankommt? Der hat dann nämlich keine weitere linke Nachbarn, und wenn du keine Überprüfung auf null und Rekursionsanker beim Löschen des Knotens hast, kann die Rekursion doch auch endlos werden.
Ein Programmierer hat immer eine Lösung. Die passt nur nicht immer zum Problem.

Hiwi für Weiterentwicklung des Lernportals (Moodle).

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: P4 - Step 4

Beitrag von linn »

des node.left is doch mein rekursionsanker.
wenn des null wird bin ich beim kleinsten.
und der stackoverflow kommt ja auch nur beim random-test.

edit: ok habs :) node=node.right hat zum löschen ned gelangt, musste die links der eltern auch ändern.

Antworten

Zurück zu „Archiv“