P5 RemoveTest

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

Ja gut, aber da ist doch der Aufwand zu groß extra die sgn-Funktion einzuführen als einfach ein "<" oder ein ">" zu benutzen.
Als Alternative für "compareTo(key) == 0" könnte man natürlich auch "equals(key)" verwenden.

Und um möglichst viele Fälle mit der remove-Funktion zu testen, könnte man sich auch eine System.out.println(this.key+key) am Anfang in den Code einbauen und einen etwas größeren vollständigen Baum entwerfen und versuchen diesen komplett zu löschen. Wenn man dann möglichst viele Löschkombinationen ausprobiert, treten im Baum auch ganz viele Spezialfälle auf, die man vielleicht nicht beachtet haben könnte. Und durch die System.out.println() kann man dann auch sehen, bis wohin die Funktion keine Fehler macht.

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

...zumindest die einzelnen Knoten sollte man mit == auf Identität vergleichen ;-)

PS: Test 3+4 schlagen immernoch fehl... -__- ...ich habe nun bereits knapp 10 Stunden mit der Fehlersuche NUR bezüglich diesem Test totgeschlagen... und so langsam bin ich "mal wieder" von diesem ach so informativen Testsystem angepisst...

WIE soll man bitte schön debuggen ohne zu wissen was denn kaputt ist?!?!?

"Preorder stimmt nicht" is ja mal ne geile Fehlermeldung... und das bei beiden fehlerhaften tests...

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

Dann kannst du ja sehr wahrscheinlich davon ausgehen, dass deine remove-Funktion nicht einwandfrei funktioniert, aber deine PreOrder-Funktion kein Problem darstellt. ;)
Vor allem deswegen, weil man bei der Implementierung von PreOrder nícht viel falsch machen kann.
Aber sicherheitshalber würde ich (falls du es noch nicht gemacht hast, ansonsten weißt du ja in welcher Funktion der Fehler liegt) PreOrder nochmal kontrollieren.
Zuletzt geändert von Skullz am 27. Mai 2007 19:28, insgesamt 1-mal geändert.

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

Skullz hat geschrieben:Dann kannst du ja sehr wahrscheinlich davon ausgehen, dass deine remove-Funktion nicht einwandfrei funktioniert, aber deine PreOrder-Funktion kein Problem darstellt. ;)
Ach.... rate mal was ich schon seit über 10 Stunden zeile für Zeile überprüfe...

Das schlimme ist ja: Egal welche testcases ich mir erstelle: alles funktioniert!

...ich bin mittlerweile dazu übergegangen zufällige bäume zu erstelllen und zufällige knoten wieder zu löschen...

ALLES klappt einwandfrei!!!

Ich hatte grad erst nen baum mit 500 Knoten -> KEIN FEHLER :-(

Wie soll ich denn das löschen "ausbessern" wenn ich nix habe um lokal zu sehen ob der algorithmus nun (nach einer änderung) klappt?

...durch die 6 Stunden "pause" im Testsystem kann man das auch nicht "mal kurz" nachgucken lassen... -__-


PS: Nur nochmal zur Sicherheit:

PreOrder war:
Wurzel, Links, Rechts
oder? ^^
Zuletzt geändert von Antragon am 27. Mai 2007 19:34, insgesamt 1-mal geändert.

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

Das sollte keineswegs eine Zurechtweisung oder ein Tipp sein, denn ich glaube dir, dass du sehr genau weißt, wo das Problem ist. Nur mach dich nicht verrückt.
Probier vielleicht mal was zu machen, das dich von Info ablenkt und denke in ein paar Stunden nochmal drüber nach. Dann fällt es dir evtl leichter.

Oder noch ein Tipp: Die besten Ideen fallen mir meistens unter der Dusche ein;)

PS: Dein PreOrder passt (oder PASSED, wenn dir das lieber ist).
Zuletzt geändert von Skullz am 27. Mai 2007 19:45, insgesamt 2-mal geändert.

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

Beitrag von ^Lara^ »

Wahrscheinlich liegts nicht daran, aber vielleicht doch ;)
Sorry an alle, die dieser baum langweilt :P

10
/
4
\
5
\
6

wenn man jetzt 4 löscht....
ist halt nicht der "einfache" fall 2.

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

Wieso nicht?
5 ist doch die Zahl, die am nächsten zur 4 ist. Also passt die auch am besten.
Also ersetzt du 4 mit 5 + sein Folgeknoten. -> Fall 2

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

Spielt das bei deiner Implementierung wirklich eine Rolle?
Nur mal so:
Was speicherst du denn so in einem BinarySearchTree alles?

Edit: Warum ist der vorhergehende Thread weg?

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

@Lara: Wenns dich zufriedenstellt... hier meine Debugausgabe: ^^

Code: Alles auswählen

=========================================
InOrder: [4, 5, 6, 10]
PreOrder: [10, 4, 5, 6]
Aktuelle Wurzel: 10 Geloescht werden soll: 4
Das linke Kind 4 im Knoten 10 wird ersetzt mit 5
PreOrder: [10, 5, 6]
=========================================
@Skuliz: Die Pausen mach ich ja sowieso ^^ ...ich hab den "eigentlichen" code ja schon seit Donnerstag fertig und nur noch diese eine Sache hat mich die letzten Tage beschäftigt...

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

Beitrag von ^Lara^ »

ich meinte einfach nur, dass man bei
10
\
12
\
14

und dem baum oben einen unterschied machen muss, auch wenn beide nur rechte Söhne haben ( vom löschenden knoten aus gesehen).
bei mir spielt das eine rolle.
falls das bei euch egal ist, umso besser.

ich speichere linker/rechter Sohn/key/data und mittlerweile auch eltern.
ist das zuviel?!

Benutzeravatar
seth2k1
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 153
Registriert: 29. Sep 2006 00:53
Wohnort: Darmstadt - Eberstadt

Beitrag von seth2k1 »

naja, es kommt denke ich auf die implementierung an. bei mir reichen söhne, key und data vollkommen
"Hallo, ich verkaufe diese modischen Lederjacken!"

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

Ich hab auch all das gespeichert, Lara... (hab ein eigenes Knotenobjekt jeweils)

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

Ich habe auch nur key, data und die beiden Kinder gespeichert.
Jedoch mach ich das bei der remove-Funktion so, dass ich von jedem Knoten aus noch eine Abfrage drin habe, die testet, ob das dem Key entsprechende Kind sich nach Weitergabe des Keys verändert hat (also gelöscht wurde) und führe dann die entsprechenden Operationen vom Elternknoten aus durch.

Wie gesagt, bei mir läuft das rekursiv. Wem's nicht gefällt, der sollte diesen Beitrag ignorieren.

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

Ich bin mittlerweile zur Überzeugung gekommen, dass meine "Lösung" richtig ist, aber der Testcase nicht damit rechnet...

Hmm... wenn ich morgen keine Lösung finde werde ich mich wohl mal an Herrn Wach wenden müssen...


Ich werde jetzt zum Spaß nochmal eine alternative Löschmethode einschicken... (sowohl meine jetzige als auch die andere sind eigentlich offiziell gültig).
Falls sich herausstellen sollte dass das Testsystem diese Lösung akzeptiert, dann ist es eindeutig ein Fehler seitens des Testsystems...

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Antragon hat geschrieben:...zumindest die einzelnen Knoten sollte man mit == auf Identität vergleichen ;-)
Nein sollte man nicht. Zum Vergleichen nimmt man ausschließlich die Methoden des Comparators.

Antworten

Zurück zu „Archiv“