Seite 5 von 5

Re: P4 - Step 4

Verfasst: 21. Jun 2009 00:16
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.

Re: P4 - Step 4

Verfasst: 21. Jun 2009 01:20
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.

Re: P4 - Step 4

Verfasst: 21. Jun 2009 01:30
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?

Re: P4 - Step 4

Verfasst: 21. Jun 2009 02:25
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.

Re: P4 - Step 4

Verfasst: 21. Jun 2009 03:45
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...

Re: P4 - Step 4

Verfasst: 21. Jun 2009 10:22
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.

Re: P4 - Step 4

Verfasst: 21. Jun 2009 12:21
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 ^^

Re: P4 - Step 4

Verfasst: 21. Jun 2009 12:31
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!

Re: P4 - Step 4

Verfasst: 21. Jun 2009 13:18
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 ^^

Re: P4 - Step 4

Verfasst: 21. Jun 2009 14:10
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 ^^

Re: P4 - Step 4

Verfasst: 21. Jun 2009 14:27
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.

Re: P4 - Step 4

Verfasst: 21. Jun 2009 21:09
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...

Re: P4 - Step 4

Verfasst: 21. Jun 2009 21:16
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 ^^)

Re: P4 - Step 4

Verfasst: 21. Jun 2009 21:29
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!

Re: P4 - Step 4

Verfasst: 21. Jun 2009 21:35
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.