P4 - Step 4

swezorke
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 10. Mai 2009 19:28

Re: P4 - Step 4

Beitrag von swezorke »

Hallo,

ich habe auch noch so meine Probleme mit der Balance:
Wir hatten ja in der Volesung, dass nach dem Löschen von Elementen der gesamte Baum von unten bis oben rebalanciert werden muss.
Wenn ich das nicht mache, sondern nur ab dem gelöschten Kntoen aufwärts balanciere, dann schlagen die Tests fehl. Wenn ich aber versuche
den gesamten Baum zu rebalancieren (rekursiv absteigen, usw.) dann brauchen die Tests viel zu lange (genau genommen weiß ich nicht mal, obs hinhaut, weil ich so lange noch nicht gewartet habe).
Wie macht ihr das denn mit dem Balancieren?

Gruß Stephan

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

Re: P4 - Step 4

Beitrag von Mark_G »

Mark_G hat geschrieben: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:
Problem gelöst! WORKS 8)

Es lag daran, dass ich removeSmallest auf den linken Teilbaum und nicht auf den rechten ausgeführt habe. Dadurch hat dann natürlich die Sortierung nicht mehr gestimmt... -.-

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

Re: P4 - Step 4

Beitrag von tanne »

swezorke hat geschrieben:Hallo,

ich habe auch noch so meine Probleme mit der Balance:
Wir hatten ja in der Volesung, dass nach dem Löschen von Elementen der gesamte Baum von unten bis oben rebalanciert werden muss.
Wenn ich das nicht mache, sondern nur ab dem gelöschten Kntoen aufwärts balanciere, dann schlagen die Tests fehl. Wenn ich aber versuche
den gesamten Baum zu rebalancieren (rekursiv absteigen, usw.) dann brauchen die Tests viel zu lange (genau genommen weiß ich nicht mal, obs hinhaut, weil ich so lange noch nicht gewartet habe).
Wie macht ihr das denn mit dem Balancieren?

Gruß Stephan
du musst nicht de GESAMTEN baum rebalancieren...sondern nur entlang des pfades den zu dem zu löschenden knoten....un wenn du diesen rekursiv suchst, kannst du auch ganz einfach diesen pfad dann rückwärts rebalancieren

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

Re: P4 - Step 4

Beitrag von VMann »

swezorke hat geschrieben:Hallo,

ich habe auch noch so meine Probleme mit der Balance:
Wir hatten ja in der Volesung, dass nach dem Löschen von Elementen der gesamte Baum von unten bis oben rebalanciert werden muss.
Wenn ich das nicht mache, sondern nur ab dem gelöschten Kntoen aufwärts balanciere, dann schlagen die Tests fehl. Wenn ich aber versuche
den gesamten Baum zu rebalancieren (rekursiv absteigen, usw.) dann brauchen die Tests viel zu lange (genau genommen weiß ich nicht mal, obs hinhaut, weil ich so lange noch nicht gewartet habe).
Wie macht ihr das denn mit dem Balancieren?

Gruß Stephan
Wenn du vom gelöschten Knoten aus aufwärts balancierst reicht das, du musst nicht nochmal durch den kompletten Baum gehen.
Wenn dein rebalance korrekt ist hast du vermutlich irgendwo beim Löschen einen Fehler.
Welche Fehlermeldung spuckt der Test bei dir denn aus?
Computer tun nicht das, was du von ihnen willst, sie tun das, was du ihnen sagst.

Benutzeravatar
anon
Neuling
Neuling
Beiträge: 10
Registriert: 16. Mai 2009 10:21

Re: P4 - Step 4

Beitrag von anon »

also ich habe das gleiche problem. glaube beim zusammenfügen des baumes klappt was nicht.
wenn der baum so aussehen würde:

.....L
.../....\.
..x......y
......../
.......K
........\
.........z

also L ist das zu löschende element und K ist das kleinste element des rechten unterbaumes.
in der rekursion gehe ich runter bis zum K und gebe als out.removed K und als out.node K.right aus.
wenn ich den baum jetzt neu zusammenfüge wie kriege ich y und z unter einen hut?
das x kommt links ans K ran und K ersetzt dann L, aber was ist mit dem y und z ?

irgendwie bin ich schon total verwirrt :D

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

Re: P4 - Step 4

Beitrag von Mark_G »

Also erst einmal wäre das kein gültiger AVL Baum... :wink:

Aber davon abgesehen:

Du setzt einfach out.node (= K.right = Z) an die Stelle von out.removed.

dan
Erstie
Erstie
Beiträge: 17
Registriert: 31. Mär 2009 13:06

Re: P4 - Step 4

Beitrag von dan »

Hm also mir ist es immer noch ein Rätsel wie ich removeSmallest rekursiv implementieren soll.
Dadurch dass ich ja einmal den entfernten Knoten und dann den restlichen Teilbaum zusammen als RemoveResult zurückgeben muss.
Ich bin bisher soweit, dass er das kleinste Element raussucht und zurückgibt, aber den Restbaum bekomm ich nicht hin...

Kann mir da jemand einen Tipp geben?

Benutzeravatar
Ibliss
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 11. Apr 2008 04:08
Wohnort: Darmstadt

Re: P4 - Step 4

Beitrag von Ibliss »

@dan
ich habe mich das auch gefraget, Antwort lautet: divide et impera
bei mir funktioniert es zumindest.

Noch etwas, wenn jemand Probleme mit balance beim RandomTest hat, soll er in rebalance überprüfen ob RR und LL Fall auch dann erkannt werden wenn ein knoten BF=+/-2 hat und einer seine Söhne (hängt vom Signum der Wurzel ob rechter oder Linker) BF=0 hat. Dieser Fall gibt es in den Folien nämlich nicht. Ich habe lange gebraucht um das herauszufinden, das komische ist dass Test 2c lief obwohl dieser Fall in meinem Code nicht berücksichtig war.

NullPointerException kommt dann wenn du auf einen Knoten zugreifst der gar nicht da ist (meistens). Ich habe eine containsNode(aNode) geschrieben in die Testklasse eingefügt und damit herausgefunden welche methode den Knoten "zufällig" vergessen hat. Es hilft. Auch habe ich eine isBalanced(tree) geschrieben bei balanceproblemen. Wenn man 5000 Knoten hat helfen solche Sachen um das Problem zu lokalisieren.
"Honesty is the first chapter in the book of wisdom.
Alien vs Predator 2 is the movie version of that book."

swezorke
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 10. Mai 2009 19:28

Re: P4 - Step 4

Beitrag von swezorke »

Ich glaube ich habe es gefunden, jedenfalls einen Fehler an dem es liegt:
Ich mach wenn ich ein Element lösche immer schön brav die Update-Funktionen bis zu dem Element, dass ich gelöscht habe. Tatsächlich muss man aber bis zu dem Element aktualiseren, dass man dann an die Stelle des gelöschten gezogen hat, also gerade das Element, das in findSmallest gelöscht wird.
Implementiert habe ich es noch nicht, aber ich melde mich nochmal, wenn ich soweit bin.

Gruß Stephan

b00m3r
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 10. Okt 2005 11:02

Re: P4 - Step 4

Beitrag von b00m3r »

Hallo zusammen,
ich hab das Grundgerüst der beiden remove Funktionen implementiert. (Fälle des Löschens und die rekursive Suche).

Zum grundsätzlichen Vorgehen.

Um einen Knoten zu löschen, muss ich ihn erstmal finden, dass ist quasi analog zum Einfügen.
Die 4 Fälle sind folgende:
1. Zu Löschender Knoten ist ein Blatt (keine Unterknoten)
2+3. Zu Löschender Knoten hat einen Linken oder rechten Unterknoten
4. Zu Löschender Knoten hat zwei Unterbäume(hier würde die removeSmallest zum Einsatz kommen. Würde sie auf den rechten Unterbaum loslassen).

Das ersteinmal zur Fallbetrachtung. Die ersten drei Fälle sollten trivial erscheinen, wenn man weiß wie man die Knoten für den Baum aktualisiert. Ich hab leider kein Plan wie. Um meine Ratlosigkeit zu demonstrieren.

Zum ersten Fall des Tests
4
/ \
3 5
Wenn ich nun Knoten 3 Löschen mag würde ich sehen ah .... der knoten is ein Blatt und ersetze die 3 mit Null.
In der Rekursion der remove Läuft das aber so, dass ich von 4 zu 3 gehe und dann 3 mein neues node ist und wenn ich dann sage alles klar Junge :) node = null
gibt er mir für den ganzen Baum null aus. Ich schaff es nicht die rekursion zu nutzen.
Kann mir da mal jemand helfen wäre toll.


Analog dazu ist das Problem bei der removeSmallest wie bekommt es hin das die Funktionen rekursiv den Baum zusammensetzt oder stückelt ihr den so zusammen? Da ist das Risiko aber ziemlich groß das man mal einen Fall übersehen hat und dann dumm aus der Wäsche schaut (wie ich gerade :))


Über konstruktive Hilfe würde ich mich sehr freuen.

Schönen Abend euch noch

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

Re: P4 - Step 4

Beitrag von zimpfer »

Zum ersten Fall des Tests
4
/ \
3 5
Wenn ich nun Knoten 3 Löschen mag würde ich sehen ah .... der knoten is ein Blatt und ersetze die 3 mit Null.
In der Rekursion der remove Läuft das aber so, dass ich von 4 zu 3 gehe und dann 3 mein neues node ist und wenn ich dann sage alles klar Junge :) node = null
gibt er mir für den ganzen Baum null aus. Ich schaff es nicht die rekursion zu nutzen.
Kann mir da mal jemand helfen wäre toll.
Ich würde sagen, der Fehler liegt darin, dass du die Rekursion beim remove mit node=remove() aufrufst, das ist aber falsch, node.left, bzw node.right=remove() muss es heißen, da sonst ja der node einfach nur mit der letzten Stufe der Rekursion ersetzt wird...

b00m3r
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 10. Okt 2005 11:02

Re: P4 - Step 4

Beitrag von b00m3r »

Nun gehen alle Tests bis auf Random :)
mal ans debuggen machen :)

swezorke
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 10. Mai 2009 19:28

Re: P4 - Step 4

Beitrag von swezorke »

Falls jemand noch ähnliche Probleme hat wie ich:
Es lag tatsächlich daran, dass ich nur ab dem entfernten Element aufwärts rebalaciert habe,
durch das Updaten des Baumes ab diesem bis zu dem Smallest-Element funktioniert alles
Prima.
Vielen Dank nochmal für die Denkanstöße.

b00m3r
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 10. Okt 2005 11:02

Re: P4 - Step 4

Beitrag von b00m3r »

Ich bin jetzt soweit, dass ich im RandomTest von 4000 Datensätze nur noch 37 drin habe. Das ist aber leicht zu erklären, weil ich den resultierenden Baum falsch zusammensetze. Heißt ich berücksichtige immer nur den rechten Nachbarn des zu löschende Elements.

Wenn ich das ganze rekursiv mache heißt den Baum in der RemoveSmallest absteigen will
node.left = removeSmallest(node.left).node;
funktioniert das so... nur wenn ich diese Zeile einfüge erhalte ich eine NPEX -.-

SCHEISSE MIT DER SCHEISSE :)

Benutzeravatar
DerInformator
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 24. Okt 2008 13:02
Wohnort: DA

Re: P4 - Step 4

Beitrag von DerInformator »

Hi,


ich habe mal die beiden Funktionen (remove() und removeSmallest() ) implementiert.... bei der remove() Funktion bin ich mir ziemlich sicher, dass ich das Konzept verstanden habe und sie (bis auf natürlich paar eventuelle leichtsinnsfehler) richtig implementiert habe.

Allerdings habe ich ziemliche Probleme mit der removeSmallest Funktion.... insbesondere wie ich den "übriggebliebenen" Baum übergeben soll ?_?

Kann mir da jemand helfen? Wie seid ihr denn so vorgegangen? So eine grobe Skizze für die removeSmallest wäre schön :)

Ach ja... ich gehe übrigens rekursiv vor...aber wahrscheinlich mache ich die Rekursion falsch :(
"Do not go where the path may lead, go instead where there is no path & leave a trail"

Antworten

Zurück zu „Archiv“