Praktikum 6

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Praktikum 6

Beitrag von marlic »

Hat schon jemand von euch das 6. Praktikum erfolgreich ins Testsystem eingereicht (das Wort "gepassed" ist wirklich schlimm ;) )?

Würde gerne mal diskutieren, ob noch an anderer Stelle, als beim Rotieren (ob man zweimal oder einmal rotiert) Freiheiten in der Implementiereung der AVL Bäume bestehen.


Bei mir liegt es gerade nämlich an der Preorder.

Ich denke mal, ein sehr einfacher test, wie 1,2,3 hinzuzufügen sollte in den Tests schon enthalten sein.

Und bei dem ist ja 2,1,3 die einzige gültige Preorder - egal welche Implementierung.

Die gibt meine Methode auch aus, aber trotzdem sind alle Tests mit "preorder falsch" durchgefallen :(

maikg2
Mausschubser
Mausschubser
Beiträge: 95
Registriert: 18. Okt 2005 22:29
Wohnort: Darmstadt

Beitrag von maikg2 »

Beim einfügen vom 1, 2, 3 ergibt sich der Baum

Code: Alles auswählen

  1
2  3
und von dem die Preorder ist 1, 2, 3.

edit: Ich nehm alles zurück und behaupte das Gegenteil!
Zuletzt geändert von maikg2 am 1. Jun 2007 13:21, insgesamt 1-mal geändert.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Nein, marlic hat eigentlich Recht. Was du da schreibst, ist kein Suchbaum.
1, 2, 3 einfügen ergibt einen entarteten Baum (3 an 2 an 1), wird dann rotiert mit 2 an der Wurzel. Also müsste Preorder 2,1,3 eigentlich richtig sein.

7mSeni
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 185
Registriert: 4. Dez 2005 12:49

Beitrag von 7mSeni »

Soweit bin ich zwar noch nicht, aber vielleicht kann mir jemand weiter helfen.
Ich habe das einfügen jetzt implementiert und es funktioniert auch für die test die ich geschrieben habe. In der aufgabenstellung steht, dass man keine Doppelrotation benutzen soll, wenn man die Wahl zwischen einfacher und doppelter rotation hat. Gilt das nur für das löschen von keys oder auch für das einfügen?
Ich habe beim einfügen nämlich doppelrotation benutzt.

Ausserdem sehe/verstehe ich nicht wann man denn die Wahl haben soll, denn die Folien gehen auf das Thema irgendwie nicht stark genug darauf ein.

Gruss

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag von marlic »

Du hast die Wahl, wenn zum Beispiel

Code: Alles auswählen

 1
  3
 2 4
Gegeben ist, also 1 die balance -2 und 3 die balance 0 hat.
Dann kann man einfach oder doppelt rotieren
(doppelt macht man sonst immer bei 2 -1 bzw -2 1 und einfach bei 2 1 und -2 -1)
"Copy & Passed"

Wahlspruch der Plagiatoren

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

mein praktikum 6 ist passed.. aber ich vesteh grade nich ganz deine frage, zumindest nach dem einfügen ist der baum eindeutig bestimmt wenn du immer rotierst sobald ein ungleichgewicht >1 auftritt. nur beim löschen glaube ich nicht, zwar nicht wegen dem rotieren da ja vorgegeben ist, dass wir und für RR oder LL im bedarfsfall entscheiden sollen, nur wenn man einen weiter oben gelegenen knoten löscht ist die frage aus welchem unterbaum man sich den ersatz holt, und da gibts dann jeweils zwei möglichkeiten die beide korrekt sind, keine ahnung in wie weit das im testsystem getestet wird. Ich hab mit "wenn links tiefer hol ersatz von links, sonst von rechts" mein passed, ob man mit zB einem grundsätzlichen "hole ersatz von rechts" auch passed kriegt weiß ich nicht, denk aber mal schon. Zumindest mit "wenn rechts tiefer hol ersatz von rechts, sonst von links", sprich im fall beide bäume sind gleich tief, kann man keine entscheidung vorgeben da beide unterbäume gleichberechtigt sozusagen sind.

Rookie
Erstie
Erstie
Beiträge: 16
Registriert: 5. Mai 2007 11:04

Beitrag von Rookie »

@marlic

Wie ganau muss ich denn bei deinem angegebenen Beispiel rotieren. Ich bin grade nämlich bei diesem Problem und frage mich, wie ich das lösen soll, da in den Follien nichts genaueres dazu erklärt ist.

Bei diesem Beispiel hat man ja oben einen BF von -2 und der rechte Sohn einen BF von 0.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

das ist eins von den beispielen was nur beim löschen entstehen kann, wo man sich aussuchen kann ob man RL oder RR auf den wurzelknoten 1 in dem fall anwendet, wir sollen laut aufgabenstellung in so einem fall einfachrotation, also RR nehmen. gespiegelt genauso, LL wenn man sich zwischen LL und LR entscheiden kann.

Rookie
Erstie
Erstie
Beiträge: 16
Registriert: 5. Mai 2007 11:04

Beitrag von Rookie »

Ok habs kapiert. Danke!

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Praktikum 6

Beitrag von blowfish »

marlic hat geschrieben: Bei mir liegt es gerade nämlich an der Preorder.
haste schon raus, woran's liegen könnte? hab nämlich n ähnliches problem. läuft alles, bis auf eine pre-order (remove4)!
an der pre-order-funktion selber wird's ja wohl nicht liegen: hab sie ja aus dem praktikum 5 kopiert.
oder gibt's wieder schöne spezialfälle zu übersehen?

PS: ich nehm beim entfernen eines knotens mit zwei nachfolgern immer den größten vorgänger als ersatz. im letzten praktikum hat das funktioniert. is dagegen was einzuwenden? in den folien steht nicht, dass man immer vom tieferen baum nehmen soll, oder hab ich was überlesen?
Zuletzt geändert von blowfish am 2. Jun 2007 01:02, insgesamt 2-mal geändert.
Ein Hemd ist Einstellungssache!

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

Beitrag von Martin K »

marlic hat geschrieben:Du hast die Wahl, wenn zum Beispiel

Code: Alles auswählen

 1
  3
 2 4
Gegeben ist, also 1 die balance -2 und 3 die balance 0 hat.
Dann kann man einfach oder doppelt rotieren
(doppelt macht man sonst immer bei 2 -1 bzw -2 1 und einfach bei 2 1 und -2 -1)
so wie es aussieht, ist so ein Test gar nicht drin.
Ich habe passed und habe diesen Fall überhaupt nicht berücksichtigt, bei mir würde hier gar nicht rotiert werden :roll:

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Beitrag von blowfish »

sehr clever von dir, das so rumzuposaunen. spätestens nächste woche gibt es so einen test und du bist plötzlich wieder failed!
Ein Hemd ist Einstellungssache!

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

Beitrag von Martin K »

ist doch praktisch:
1. hab ich's schon korrigiert
2. brauch ich dann kein revoke

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Beitrag von blowfish »

ok, is was dran!
Ein Hemd ist Einstellungssache!

qveXx
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 2. Dez 2005 19:02

Beitrag von qveXx »

Nur mal so ne Frage, dass ich nichts falsch verstanden hab.
1. Wieso habt ihr die Wahl bei
1
3
2 4
zwischen einfach und doppelt rotation? Meiner Meinung nach kommt da nur doppelt rotation in Frage.

2. Der Baum hätte doch schon früher rotiert werden müssen, also als er noch so
1 1
3 oder 3
2 4

aussah.

PS: kA wieso mein Baum in der Vorschau halbwegs lesbar dargestellt wird, aber hier nicht ;)

Antworten

Zurück zu „Archiv“