P4 - Step 4

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Re: P4 - Step 4

Beitrag von Gnomix »

@Boomer:
removeSmallest() liefert nicht nur einen Baum, sondern einen Knoten und einen Baum ohne diesen Knoten.
Und node.left solltest du nicht durch ein element von removesmallest() ändern müssen.

Benutzeravatar
misafir
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Okt 2008 05:13

Re: P4 - Step 4

Beitrag von misafir »

Wie mein Vorredner sagte, du übergibst bei RemoveSmallest einen Knoten und einen Baum.
Undzwar den kleinsten Knoten und den Restbaum nachdem man diesen Knoten aus dem Baum gelöscht hat.

Was bei vielen das Problem ist, dass der zurückgegebene Baum nicht der ganze Restbaum ist. Sondern nur der Letzte Teil.
Dh. du musst den Baum rekursiv wieder zusammenflicken.

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

Re: P4 - Step 4

Beitrag von DerInformator »

misafir hat geschrieben: Dh. du musst den Baum rekursiv wieder zusammenflicken.
genau das ist mein Problem denke ich ... ich weiß nicht wie...

also ich hab das so gemacht (ist aber offensichtlich falsch ^^)

Wenn Linker Sohn vom Knoten != null
=> Rekursion mit node.left
(wenn er mit Rekursion fertig ist geht er ja da jetzt weiter...und hier will ich ja den Baum wiederherstellen) :
node.left = out.node;
out.node = node;

Wenn Linker Sohn vom Knoten == null
=>
Füge ihn zu out.removed hinzu
out.node = node.right;
gebe "out" aus

ganz zum schluss nochmal gebe ich "out" aus

PS: kann man das auch irgendwie ohne Rekursion lösen? z.B. mit while Schleife?
"Do not go where the path may lead, go instead where there is no path & leave a trail"

dumbo2
Neuling
Neuling
Beiträge: 9
Registriert: 20. Mai 2009 20:05

Re: P4 - Step 4

Beitrag von dumbo2 »

Sieht doch soweit schon mal ganz gut aus.

Du musst natürlich noch rebalance, updatebiggest und updateheight einfügen, jedesmal wenn du den Baum am Ende einer Rekursion zusammenflickst. Ob du dabei auf out.node oder node arbeitest ist eigentlich egal.

Wenn du den zu löschenden Knoten gefunden hast, musst du natürlich auch den Fall abdecken, dass kein rechter Unterbaum vorhanden ist, falls einer da ist, fügst du ihn wie von dir beschrieben ein und updatest wiederrum rebalance, height und biggest.

Benutzeravatar
misafir
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Okt 2008 05:13

Re: P4 - Step 4

Beitrag von misafir »

DerInformator hat geschrieben:
misafir hat geschrieben: Dh. du musst den Baum rekursiv wieder zusammenflicken.
genau das ist mein Problem denke ich ... ich weiß nicht wie...

also ich hab das so gemacht (ist aber offensichtlich falsch ^^)

Wenn Linker Sohn vom Knoten != null
=> Rekursion mit node.left
(wenn er mit Rekursion fertig ist geht er ja da jetzt weiter...und hier will ich ja den Baum wiederherstellen) :
node.left = out.node;
out.node = node;
sieht doch wirklich ganz gut aus. ich hoff du definierst vor node.left=out.node noch das out.
und vergiss nicht die baumhöhe, das biggest end und rebalance anzuwenden.
was genau ist den bei dir das problem? zuviele bäume, zuwenige? überhauptkeine? anzahl

bzgl des zusammenflickens..
du flickst den baum wie oben zitiert mit node.left=out.node (der rest baum aus der jeweiligen rekursion) und deinem out.node = node..
falls das nicht hinhaut probier out nochmal am ende ganz neu mit gelöschtem knoten und node zu definieren.
also da wo du out.node=node stehen hast-> out = new...

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Re: P4 - Step 4

Beitrag von Gnomix »

Hmm, also ich habe Removesmallest das anders gelöst.

1. speichere node in current.
2. suche per while schleife kleinesten knoten und speichere den in current.
3. lösche current aus node per remove().
4. gebe result (node, current) zurueck.

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

Re: P4 - Step 4

Beitrag von DerInformator »

@ Gnomix
das ist ja interessant ... du wendest in remove() die removeSmallest() auf und in removeSmallest() die remove() auf ^^
aber stimmt, du hast recht, das kann man hier so machen, da in der removeSmallest dein "zu removender" Knoten nie 2 Kinder hat. (so dass du halt keine endlos-gegenseitig-aufrufe hast)

@ alle anderen ^^
Danke für die Hilfen... habe das glaube ich hinbekommen... zumindest laufen alle Tests bis auf Random
Da bekomme ich die Meldung <4000> expected but was found <0> ^^ hehe.... ich lösche also irgendwie alle Knoten :D

Aber dazu lese ich mir nochmal diesen Thread durch...ich glaube der eine oder andere hatte schon mal das gleiche Problem ^^
"Do not go where the path may lead, go instead where there is no path & leave a trail"

samy-delux
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 21. Okt 2008 18:59

Re: P4 - Step 4

Beitrag von samy-delux »

DerInformator hat geschrieben:Danke für die Hilfen... habe das glaube ich hinbekommen... zumindest laufen alle Tests bis auf Random
Da bekomme ich die Meldung <4000> expected but was found <0> ^^ hehe.... ich lösche also irgendwie alle Knoten :D
Dein Problem dürfte sein, dass im Random Test auch irgendwann mal die Wurzel entfernt wird. Wahrscheinlich wird dieser Fall bei dir nicht richtig behandelt!

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

Re: P4 - Step 4

Beitrag von DerInformator »

arrrrghhh ><

zum verrücktwerden ... <4000> expected but was found <4001> :D

um einen Knoten falsch :mrgreen: ..... na warte doofer Knoten ....ich krieg dich noch ^^

Edit: Jawohl ^^ den Knoten gefunden und eliminiert .. es funzt nun ^^
"Do not go where the path may lead, go instead where there is no path & leave a trail"

Liox
Neuling
Neuling
Beiträge: 3
Registriert: 17. Jun 2009 18:14

Re: P4 - Step 4

Beitrag von Liox »

"Der Nächste bitte"
"Jo, Hi! Ich hab ein Problem ^^"

Heflt mir mal kurz ob ich vom Konzept her es ca. richtig habe:

remove
Wenn Knoten gefunden
wenn keine Söhne
node = null;
wenn ein Söhne
node = node.right/node.left;
wenn zwei Söhne
Baum rS = removeSmallest(node.right).removed;
(Baum mit dem kleinsten Knoten aus dem rechten Unterbaum als Wurzel wird angelegt)
Rechter rS-Unterbaum ist removeSmallest(node.right).node; <------- Nullpointer :(
Linker rS-Unterbaum = node.left

in allen if-cases sind rebalance(node), updateHeight(node) und updateBiggest(node) enthalten

Ansonsten (Wurzel ist nicht der gesuchte Knoten), wie bei add vergleich der Intervalstartgrößen für links/rechts, falls gleich nach agentennamen rechts oder links

return node;

removeSmallest
Speichere neuen, leeren Baum removed
wenn linker Unterbaum != null
speichere node.left als removeSmallest(node.left).node
führe removeSmallest(node.left) aus
wenn linker Unterbaum == null
speichere node als removed
wenn rechter Unterbaum != null
speichere node.right als node
wenn rechter Unterbaum == null
speichere node als null

return new RemoveResult (removed, node);


So sieht mein Konzept aus.
Testresultat: testOne bestanden, testRemoveRoot und testRandom Nullpointer, rest failed T_T
Wer alle Fehler findet, bekommt nen Kecks ^^

Benutzeravatar
misafir
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Okt 2008 05:13

Re: P4 - Step 4

Beitrag von misafir »

Liox hat geschrieben: removeSmallest
Speichere neuen, leeren Baum removed
wenn linker Unterbaum != null
speichere node.left als removeSmallest(node.left).node
führe removeSmallest(node.left) aus
wenn linker Unterbaum == null
speichere node als removed
wenn rechter Unterbaum != null
speichere node.right als node
wenn rechter Unterbaum == null
speichere node als null

return new RemoveResult (removed, node);


So sieht mein Konzept aus.
Testresultat: testOne bestanden, testRemoveRoot und testRandom Nullpointer, rest failed T_T
Wer alle Fehler findet, bekommt nen Kecks ^^
Wenn linker baum !=null:
speichere removesmallest(node.left) erstmal als removeresult ab damit du nicht mehrmals removesmallest aufrufst und dadurch nen falsches ergebniss hast.
node.left=gespeichertesremoveresult.node
bezüglich des "führe removeSmallest(node.left) aus"? versteh ich nicht ganz, wäre dann ja doppelt gemoppelt. machste doch schon oben mit der zuweisung von node.left=gespeichertesremoveresult.node.
du musst aber noch den baum "zusammenflicken", mit einem removeresult ( unserem return removeresult ) der den gelöschten knoten + unseren aktuellen restbaum enthält (welcher wiederrum bedingt durch die rekursion und die zuweisung node.left=gespeichertesremoveresult.node auf den restbaum der einen unterstufe zeigt und dadurch rekursiv alles von unten nach oben "geflickt" wird).


und die anderen abfragen sind überflüssig da du sie ja schon in remove machst,
ein einfaches else reicht aus.

zerofs2001
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 28. Nov 2008 15:53

Re: P4 - Step 4

Beitrag von zerofs2001 »

DerInformator hat geschrieben:arrrrghhh ><

zum verrücktwerden ... <4000> expected but was found <4001> :D

um einen Knoten falsch :mrgreen: ..... na warte doofer Knoten ....ich krieg dich noch ^^

Edit: Jawohl ^^ den Knoten gefunden und eliminiert .. es funzt nun ^^
Wie hast du denn diesen einen Knoten gefunden??? Ich hab 6 zu viel und ich habe gemerkt das ich aus irgendeinem Grund 6 Knoten nicht korrekt finde und entsprechend nicht lösche...

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

Re: P4 - Step 4

Beitrag von DerInformator »

zerofs2001 hat geschrieben:
DerInformator hat geschrieben:arrrrghhh ><

zum verrücktwerden ... <4000> expected but was found <4001> :D

um einen Knoten falsch :mrgreen: ..... na warte doofer Knoten ....ich krieg dich noch ^^

Edit: Jawohl ^^ den Knoten gefunden und eliminiert .. es funzt nun ^^
Wie hast du denn diesen einen Knoten gefunden??? Ich hab 6 zu viel und ich habe gemerkt das ich aus irgendeinem Grund 6 Knoten nicht korrekt finde und entsprechend nicht lösche...
Naja ... ich denke das war eher eine Dummheit in meinem Code... ich habe falsch nach den Agentennamen gesucht... ist mir später erst aufgefallen, dass ich String1.compareTo(String2) benutzen kann :(

Aber das ist jetzt sehr schwer zu sagen, wo bei dir der Fehler liegen könnte ?!? Versuche mal den "Randomchen-Test" mit einzubauen und den zu debuggen (Seite 1 oder 2 dieses Threades)... das hat mir z.B. geholfen...

Wie hast du den deine removeSmallest() gebaut? hab so ein gefühl das diese Funktion bei sehr viel Leuten Probleme macht (inklusive mir ^^)
"Do not go where the path may lead, go instead where there is no path & leave a trail"

zerofs2001
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 28. Nov 2008 15:53

Re: P4 - Step 4

Beitrag von zerofs2001 »

Also mein smallest sieht wie folgt aus:

ich teste ob es einen nachfolger gibt, für denf all das das kleinste linke der direkte rechte des zu löschenden knoten ist und gebe entsprechend das result mit dem direkten rechten nachbarn und dem rechtenrechtennachbarn zurück.

falls es mindestens einen linken teilbaum gibt, sucht er diesen solange bis es keinen linken teilbaum mehr gibt.
dann gebe ich das removeresult mit dem kleinsten linken und remove(node, aktuell.interval, aktuell.agent) zurück.
node ist hier der ursprüngliche baum und aktuell ist der kleinste linke.

randomchen funktioniert übrigends. wobei ist ja nicht sicher ob mein programm da auch richtig löscht. ich werde das mal checken!

Benutzeravatar
misafir
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Okt 2008 05:13

Re: P4 - Step 4

Beitrag von misafir »

zerofs2001 updatest du auch die höhe und checkst die balance wenn du löschst ? musst du ggf mehrmals machen.
ansonsten sind die fälle wie man beim löschen vorzugehen hat im skript 09 Suchbäume, ab Seite 14 angegeben.

Antworten

Zurück zu „Archiv“