P4 - Step 4

[Vockilein]

Ich steh grad irgendwie auf dem Schlauch:

- Wozu brauch ich removeSmallest()? Ich hab noch keine Verwendung gefunden.

- Bei remove() macht man doch folgendes:

1. Ich geh rekursiv durch den Baum bis ich bei meinem Knoten bin den ich löschen will.
2. Hab ich den Knoten gefunden. Lösch ich ihn und füg den Rest wieder ein.

Jetzt hab ich das Problem das er bei mir irgendwie keinen Knoten löscht... Da kommt immer die Meldung:

Code: Alles auswählen

junit.framework.AssertionFailedError: two left expected:<2> but was:<3>

Wenn jemand nen Tipp hat wär das gut Sonst sitz ich noch nen Tag an Step 4

[Jonathan]

Was machst du denn wenn der zu löschende Knoten 2 Kinder hat?

[Vockilein]

Mist da brauch ich das removeSmallest() ich hab grad eben erst in die Folien geschaut davor nur in alle möglichen anderen Sachen.

Was mich aber wunder das sogar mein Test removeLeft fehlschlägt und er anscheinend nichts löscht... Sehr komisch. Ich werd wohl nochmal neu strukturiert anfangen

[Heap]

Hi,
komme bei diesem Problem nicht weiter.
Es laufen alle Test bis auf den random Test.

Die Fehlermeldung ist, dass ich anstatt 4000 nur noch 3 Elemente habe. (Im random test werden ja erst 5000 zugefügt und dann 1000 wieder entfernt)

Habe mal geschaut, der Baum mit den 5000 Knoten wird (keine Ahnung ob wirklich richtig, aber size ist dann 5000) aufgebaut.

dann habe ich nach relativ wenigen Schritten nur noch 3 Knoten und danach passiert nix mehr.

Ich gehe folgendermaßen vor:
Am anfang meiner remove mehtode habe ich die Zuweisung

Code: Alles auswählen

helpNode = node.

Dann such ich entlang dem Baum mit einer Schleife. Also:

Code: Alles auswählen

if (helpNode == gesuchter Knoten) break;
else je nachdem ob gesuchter größer oder kleiner helpNode = helpNode.left oder helpNode.right

Wenn der Wert gefunden wurde schaue ich mir den parent von helpNode an und 'lösche' den gesuchten Knoten, indem ich entweder den einzigen Sohn, den In-Order sohn oder null an die entsprechende Seite von parent hänge.
dann rebalanciere ich entlang dem WEg zur Wurzel und gebe dann node zurück.
Wenn der Wert nicht gefunden wurde gebe ich node zurück ( node müsste ja noch auf die ursprüngliche Wurzel zeigen ??)

Wahrscheinlich wird der Fehler da liege, dass ich einen Denkfehler habe, auf welchem Objekt ich arbeite, aber welchen?
Gruß

[robert.n]

Ich hatte mal ein ähnliches Problem (verschwindende Knoten) und wenn ich mich noch richtig erinnere lag es daran, dass ich bei manchen rekursiven Aufrufen einfach nur geschrieben habe:

funktion(node, ...)

anstatt

node = funktion(node, ...)

Das Problem bei diesem Praktikum sind halt echt die vielen Rekursionen, da kann man nur sehr schwer debuggen.^^

MfG, Robert

[Le_Coeur]

Bei 4 kann man auch ohne Rekursion machen:)
P.S. Wie lange laeuft mit Rekursion?

[Niggi]

das lustige bei mir ist, alle test ohne random laufen durch aber bei random, löscht er einfach gar nichts , es verbleiben 5000 von 5000 knoten und ich weiß nich warum LOL

[André R.]

Könnte mal jemand ein paar Sachen zu einer groben Abfolge von remove sagen?

Mir ist der Sinn von remove Smallest in Verwendung mit remove nicht klar, warum soll ich den kleinsten löschen? Und was habe ich davon den gelöschten Knoten ebenfalls zurück zu geben?

Bei mir gehen momentan mit remove (rekursiv) alles bis auf random - er löscht dort scheinbar gar nichts ?!
Jemand ne Idee?

[dk1001]

Abfolge beim Löschen: Die Folien geben wie üblich tipps: Löschen ist erstmal wie hinzufügen: Du musst erstmal die Stelle finden an der sich der Knoten befindet und die findet sich am besten, wenn man so tut wie als wolle man den Knoten einfügen mit dem Unterschied, dass es jetzt sein kann (lies: es sollte sein), dass man jetzt den gleichen Intervalstart und Agentenname gefunden hat und diese eben löschen muss...

für alle mit Problemen mit dem RandomTest beim löschen:
Beim Löschen gibt es 4 Fälle: Der Erste ist, dass der zu löschende Knoten ein Blatt ist (keinen rechten und linken Unterbaum). Der Vierte ist, dass der Knoten sowohl einen linken als auch einen rechten Unterbaum hat. Die zwei Anderen verhalten sich symetrisch und sollten nicht schwer zu erraten sein
Alle Tests außer dem Random kümmern sich aber nur um den ersten und den vierten Fall...

removeSmallest wirst du nur im vierten Fall brauchen (eventuell auch im Dritten, das wäre aber Overkill - Bonusfrage: Warum?) - warum und wieso und weshalb, deswegen sollte man sich die Folien noch mal ganz genau ansehen. Da werden zwei Taktiken besprochen wie das Löschen von Knoten funktioniert die einen linken und rechten Unterbaum haben - die eine würde ein removeBiggest benötigen, die andere ist eben jene die wir implementieren sollen und benötigt removeSmallest ... stell dir einfach mal die Frage wie du es hinkriegst die beiden Unterknoten wieder mit dem Rest des Baumes zu verbinden - man müsste den zu entfernenden Knoten mit irgendeinem anderen ersetzen, welcher Knoten da wohl die richtige Wahl wäre?

[André R.]

Okay, dann mache ich die Funktion von smallest direkt in remove.

Wenn der random Test nicht geht, muss es also wohl ein Problem mit kein linker bzw kein rechter sohn eines zu löschenden Knotens sein, allerdings habe ich da mal mit einem eigenen Testfall auch überprüft ... keine Probleme ..

Jemand noch ne Idee warum er bei random NICHTS löscht? (5000 von 5000 übrig)
Gibts da ein besonderes Problem mit height/rebalance etc?

[Niggi]

habe gleiches problem ... eigentlich behandle ich die oben 4 beschriebenen fälle auch , aber irgendwie löscht er nichts und ich weiß noch nich so recht warum ......#


EDIT : wie ich beim debuggen jetzt festgestellt hab, finde ich beim rekursiven Durchlauf GAR keinen Knoten der bei mir auf x.agent = node.agent && x.start == node.interval.start passt ?!?! und ich check nich warum .... ich geh rekursiv tiefer wie bei add() weil löschen ja erstmal wie einfügen ist

[O_kut]

könnte es sein, dass ihr in eurer Remove-Funktion zum Vergleichen von Strings String1==String2 verwendet, anstelle von String1.equals(String2) ?

Dass trotzdem die kleineren Tests bestanden werden, könnt ihr hier nachvollziehen:
http://www.java-blog-buch.de/0302-strings-vergleichen/

[André R.]

Den Fehler hatte ich tatsächlich (obwohl ich es z.b. in add richtig hatte .. naja °_°) , nun löscht er immerhin 10 Stück .. sprich expected 4000 but was 4990.

Wie geht ihr denn im Fall kein linker oder kein rechter Sohn mit Höhe etc um? Vielleicht liegt da ein Problem ...

[Mark_G]

Warum hat removeSmallest zwei Rueckgabewerte? Der erste (der kleinste Wert) ist klar... aber was ist mit der neuen Wurzel gemeint???

PS: Wird die Methode remove() bei euch auch monstermaessig lang? Ich hab da krass viele Fallunterscheidungen (parent == null oder nicht (also der Fall, dass es der oberste Knoten ist), parent.left == currentNode oder parent.right == currentNode (um zu wissen, ob ich parent.left oder parent.right zu aendern brauche)... und ich hab bisher keine Moeglichkeit gefunden, es kuerzer zu machen.

[ivoch]

Warum hat removeSmallest zwei Rueckgabewerte? Der erste (der kleinste Wert) ist klar... aber was ist mit der neuen Wurzel gemeint???

Wenn du einen Knoten löscht, musst du ihn ja mit dem kleinsten Knoten vom rechten Teilbaum ersetzen (oder größtem vom linken Teilbaum, das wird aber im Praktikum nicht gebraucht). Also musst du den kleinsten Knoten aus diesem Teilbaum löschen, ihn an der Stelle des tatsächlich zu löschenden Knoten einfügen, und als rechten Teilbaum den vorherigen rechten Teilbaum, aber eben ohne den kleinsten Knoten - was genau der zweite Rückgabewert von removeSmallest ist.



remove() ist zwar länger als ein paar Zeilen, aber monstermässig muss sie nicht sein. Viele deiner Abfragen sind bestimmt überflüssig oder lassen sich zusammenführen. Z.B. warum willst du wissen, ob der Knoten wie Wurzel ist oder nicht? Und parent.left/right - das ist bestimmt auch nicht unbedingt notwendig: wenn du z.B. rotateLeft(currentNode.right) aufrufst und dann in der Methode rotateLeft dem Parameter einen anderen Wert zuweist, dann wird der rechte Sohn von currentNode (also currentNode.right) auch entsprechend geändert, obwohl die rotateLeft Methode gar nichts vom currentNode weist. Sprichwort "Zeiger" und keine Kopien (bei Operationen mit Objekten - bei Operationen mit Primitiven werden bei Übergaben und Zuweisungen tatsächlich Kopien erstellt und diese sind dann automatisch vom Original unabhängig).


[EDIT] Und ich bin mir nicht ganz sicher, aber "parent" wird in der Klasse Tree gar nicht gespeichert, oder? Hast du den Attribut extra hinzugefügt oder was? Es ist zwar nicht grundsätzlich falsch, aber überflüssig und macht deine Implementierung fehleranfälliger, denn je mehr Attribute deine Klasse hat, desto wahrscheinlicher es ist, dass du irgendwann mal vergisst, den einen oder anderen korrekt zu ändern und dann kommt alles durcheinander.

Ein Zeiger auf den Elternknoten in einem Baum kann natürlich auch nützlich sein, z.B. wenn du (aus welchem Grund auch immer) die Kanten von den Blättern zur Wurzel entlang verfolgen willst aber hier ist das nicht notwendig.