P5 RemoveTest

Alexis1987
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 29. Apr 2007 16:58

P5 RemoveTest

Beitrag von Alexis1987 »

Hallo,

bei mir schlägt ,testRemove5 und testRemove6 fehl.

"natürlich" kann ich mir das nicht erklären, da ich "natürlich alle" Testfälle abdecke.

Im grunde gibt es ja nur 3,4,6 oder 8 Testfälle , je nach Implemetierung.

Meine fehlermeldung lautet bei beiden: "Anzahl der Schl%uFFFDssel im Baum stimmt nicht".

So zunächst wie findet der Veranstalter das raus?
Ich gehe einfach mal davon aus, das er sich die In-/Pre-/Post-Order-Liste ausgeben lässt und die werte darin vergleicht.

Da mein Remove ja meiner Meinung nach funktioniert, könnte es auch ein Fehler innerhalb der In-/Pre-/Post-Order-Liste sein.

Da kommt aber nur eine Stelle in Frage, und hier liegt mein Problem:
Wenn der Baum leer ist, sprich die Wurzel als einziger Knoten wurde gelöscht,
sollen die "Order"-Methoden dann eine leere Liste zurück geben (der momentane Stand) oder einfach nur null ??

Wie habt ihr es denn gemacht?? Und bei wem ist es dann auch "Passed" ??

Eben nochwas eingefallen:
Wenn das Testprogramm auf eine andere, nicht spezifizierte, Art auf den Baum zugreift um heraus zu finden wie viel Knoten sich noch darin befinden, dann ergibt sich doch eine nicht genannte Einschränkung in der Implementierung, da es dann einen Unterschied machen könnte ob man einen "ROOT-Knoten" nutzt oder ob man sagt die Wurzel kann nie gelöscht werden, nur überschrieben und der baum ist leer wenn wurzel.key == null.

Dann hätte man je nachdem entweder n+1 Knoten im Baum oder n, wobei n die anzahl der vom Testprogramm eingegebenen Knoten ist.
[edit]ums genau zu machen wenn n == 0 ist in beiden fällen 1 Knoten vorhanden[/edit]
Danke fürs durchlesen

Gruß Alexis
Der Tofu-Burger schmeckt ausgezeichnet, wenn man ihn Kurz vor dem Verzehr durch ein saftiges T-Bone-Steak austauscht.

debach
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mai 2007 15:59
Kontaktdaten:

Beitrag von debach »

Das Problem hatte ich auch. Prüfe, wie du folgenden Fall abdeckst (falls du den größten untergeordneten Knoten als Ersatz nimmst):

Code: Alles auswählen

                    1
                        50
                25            75
           10       40
         5        35
       2        30
Was tust du, wenn du 50 löschst? Es müsste 40 an die Stelle von 50 und 35 an die Stelle von 40 gestellt werden.
Mit anderen Worten: Der Parentalknoten (25) des Ersatzknotens (40) erhält den linken Unterbaum (35 u. 30) des Ersatzknotens. Schau mal nach, ob du diesen Fall bedacht hast. Mich hat es auch die ein oder andere Stunde gekostet.

Ich hoffe, man kann den angedeuteten Baum erkennen.

Alexis1987
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 29. Apr 2007 16:58

Beitrag von Alexis1987 »

Hallo, danke für die schnelle Antwort,

ich verstehe was du meinst, gleich mal testen was der da macht.

Bis gleich.
Der Tofu-Burger schmeckt ausgezeichnet, wenn man ihn Kurz vor dem Verzehr durch ein saftiges T-Bone-Steak austauscht.

Benutzeravatar
Wang Tang
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 5. Dez 2006 17:57

Beitrag von Wang Tang »

Da kommt aber nur eine Stelle in Frage, und hier liegt mein Problem:
Wenn der Baum leer ist, sprich die Wurzel als einziger Knoten wurde gelöscht,
sollen die "Order"-Methoden dann eine leere Liste zurück geben (der momentane Stand) oder einfach nur null ??
Leere Liste: Ich hatte beim ersten Upload eine Liste mit nur einem null-Eintrag -> failed. Auf leere Liste umgestellt -> passed :)

Alexis1987
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 29. Apr 2007 16:58

Beitrag von Alexis1987 »

Hy,

das wirds gewesen sein.

also nochmal Danke.

gut das ich das "natürlich" in weiser vorraussicht in anführungsstriche gesetzt habe ;)

Gruß Alexis
Der Tofu-Burger schmeckt ausgezeichnet, wenn man ihn Kurz vor dem Verzehr durch ein saftiges T-Bone-Steak austauscht.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

hm, ich hab sogar ne NullPointerException werfen lassen wenn der Baum leer ist un bin passed, naja, dafür kann ich dann ma revokation ausprobieren

yagami
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 5. Okt 2006 03:02

Beitrag von yagami »

weisst jemand von euch wie die RemoveTeste durchgeführt werden? probiert es Post/In und Pre in jedem test aus(wenn ja in welchen Reihenfolge?) oder nur eine davon für jede...ich bekomme ein fehler bei Test 3,4 und 5 aber weiss ich nicht ob das Problem liegt bei der Remove methode oder die PreOrder methode:

Testcase: testRemove3 took 0.009 sec
FAILED
Pre-Order stimmt nicht
junit.framework.AssertionFailedError: Pre-Order stimmt nicht
at RemoveTest.testRemove3(Unknown Source)

Testcase: testRemove4 took 0.004 sec

Benutzeravatar
Martin K
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 110
Registriert: 13. Okt 2006 17:56

Beitrag von Martin K »

Genau so einen Fehler hatte ich auch, muss an remove liegen.
(bei PreOrder kann man ja nicht viel falsch machen :wink: )

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

Beitrag von Antragon »

Bei mir schlägt auch der Preorder-Test fehl...

Das das "Preorder" an sich richtig funktioniert habe ich mittlerweile an ziemlich vielen Tests überprüft...

Beim Löschen gibt es ja zwei möglichkeiten für innere Knoten:
1. Den kleinsten Knoten des rechten Teilbaums nehmen
2. Den größten Knoten des linken Teilbaums nehmen

Ich selbst probiere immer erst 1 und danach erst 2 aus.

Das Löschen funktioniert auch ohne jegliche Probleme in allen Testcases die ich hatte...

Kann es etwas ausmachen, dass ich 1. bevorzuge?

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

Beitrag von Skullz »

@Antragon
Nein, es kann nicht daran liegen, dass du eine Methode bevorzugst, denn beide sind in allen Situationen gültig.
In meiner Implementierung ist das auch so und die ist ohne Probleme durchgelaufen.

Also überlege dir, welche Problemfälle es geben könnte (z.B. wenn du den Wurzelknoten entfernen willst;)).

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

Beitrag von Antragon »

Jojo... hatte eine doofe Stelle gefunden... da wurde noch eine Verknüpfung offensichtlich nicht aktualisiert ^^ ...allerdings rätsel ich schon seit einer Stunde daran rum WO die Verknüpfung nicht gesetzt wird *g*

ZERG
Mausschubser
Mausschubser
Beiträge: 59
Registriert: 19. Apr 2005 16:37

Beitrag von ZERG »

aloa´he

Das mit der Ausgabe der Order-Listen (leeren Liste wenn keine Knoten vorhanden sind) habe ich noch nicht richtig verstanden. Mein Codeabschnitt (ohne detailierte implementierung) sieht so aus:

Code: Alles auswählen

public List<Key> getPostOrder() {
		List<Key> postorder = new ArrayList<Key>();

		if (this.links != null) {
			mache postorder ;)
		}
		if (this.rechts != null) {
			mache postorder ;)
		}

		// test ob es key gibt?!
		if (this.key != null) {
			postorder.add(this.key);
		}
		return postorder;
	}
Sollte ich vielleicht vor dem Erstellen der "new ArrayList" auf (this.key !=null) testen?
Oder was muss ich zurückgeben?

Außerdem, kann mir jemand sagen, wodurch dieser Fehler auftreten könnte?

Code: Alles auswählen

Testcase: testRemove1 took 0.014 sec
	FAILED
Anzahl der Schl�ssel im Baum stimmt nicht
junit.framework.AssertionFailedError: Anzahl der Schl�ssel im Baum stimmt nicht
	at RemoveTest.testRemove1(Unknown Source)

Lösche ich etwa nicht richtig? Die Testcases für die Orders laufen alle durch.

Benutzeravatar
Wang Tang
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 5. Dez 2006 17:57

Beitrag von Wang Tang »

Code: Alles auswählen

      if (this.key != null) {
         postorder.add(this.key);
      } 
Da hatte ich das if nicht, weswegen der mir in einen leeren Baum "null" in die Liste reingehauen hat. Und deswegen hatte ich auch deinen Fehler (Anzahl der Schlüssel im Baum stimmt nicht). Die ArrayList musst du so oder so erstellen, weil du sonst evtl. null zurückgibst.

Aber da du das "if" drin hast, muss der Fehler eigentlich im remove liegen.

Erebos
Mausschubser
Mausschubser
Beiträge: 47
Registriert: 27. Apr 2007 00:51

Beitrag von Erebos »

Bei schlägt jeder RemoveTest fehl, aber ich weiß nicht warum
Mit meinen eigenen Testcases klappt es wunderbar.
Bei jedem Test wird wohl ein NullPointer geworfen, aber jeder versuch was zu löschen bei mir gibt keinen NullPointer.
Bei falschen Werten werfe ich IllegalArgumentException
Und bei Schlüsseln außerhalb KeyNotInTreeException

Wenn es zum Verschieben kommt, nehmen ich immer den größten linken Nachfolger und passe dessen Nachfolger an, ist das etwa falsch?

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

Beitrag von Skullz »

@Erebos
Was passiert, wenn du die Werte eines Knotens löschst und dieser Knoten links keinen Unterbaum hat?

Antworten

Zurück zu „Archiv“