Frage zu Übung 12 (Rot-Schwarz Bäume)

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von Steven »

Das wird eigentlich durch den Pseudocode zu RB-DELETE bereitsbeantwortet: Im Block von Zeile 1 bis 3 wird y entweder auf den übergebenen Knoten oder auf dessen Nachfolger gesetzt. Danach wird y nicht mehr verändert. In Zeile 16 erfolgt dann die Prüfung, ob dieses y schwarz ist -> dann wird Fixup aufgerufen.
Der Check geht also auf den Knoten, der wirklich aus dem Baum gelöscht wird, nicht auf den übergebenen "eigentlich zu löschenden" Knoten.

Telefonjoker
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 19. Apr 2008 21:02

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von Telefonjoker »

Steven hat geschrieben:Das wird eigentlich durch den Pseudocode zu RB-DELETE bereitsbeantwortet: Im Block von Zeile 1 bis 3 wird y entweder auf den übergebenen Knoten oder auf dessen Nachfolger gesetzt. Danach wird y nicht mehr verändert. In Zeile 16 erfolgt dann die Prüfung, ob dieses y schwarz ist -> dann wird Fixup aufgerufen.
Der Check geht also auf den Knoten, der wirklich aus dem Baum gelöscht wird, nicht auf den übergebenen "eigentlich zu löschenden" Knoten.
Ja, so sehe ich das auch. Dass der Nachfolger seine Farbe mitnimmt.
Sonst könnte man ja einfach nach farbe[z] fragen.

Telefonjoker
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 19. Apr 2008 21:02

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von Telefonjoker »

hmm kommt nicht mehr...???

Dann nochmal:

Also, wenn ich einen Knoten x lösche und an dessen Stelle den Knoten y setze, dann nimmt y seine Farbe mit.
Wenn x schwarz war und y rot, dann ist nach dem Ersetzen y immer noch rot.

Stimmt's?

Was ich mich jetzt noch frage ist, was passiert, wenn der Elternknoten von x auch rot war?
Dann ist das neue Kind y vom Elternknoten auch rot; was ja nicht sein darf.
Was passiert jetzt? DeleteFIXUP wird ja nicht aufgerufen...

xilef
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Jan 2008 04:47

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von xilef »

Hi Telefonjoker

Also wenn du mit
an dessen Stelle den Knoten y
meinst, dass y der Nachfolger von x ist und x innerer Knoten mit zwei Kindern gelöscht wird dann stimmt deine Aussage nicht.
In diesem Fall wird nur der KEY ersetzt und RB-DELETE-FIXUP wird mit dem rechten Kind aufgerufen.
In diesem Fall wären deine weiteren Fragen hinfällig, da auf den Roten Elter ein schwarzer Knoten folgt.

Falls ich daneben liege erkläre mir bitte genauer welche Situation bei dir eintritt.

grüße,
xilef

Telefonjoker
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 19. Apr 2008 21:02

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von Telefonjoker »

also, wenn in Übung 12 G1 zuerst den Knoten 12 löschen wurde; dann hätte ich von der Wurzel den Pfad 38schwarz -> 19rot -> 8schwarz. Richtig?
Und FIXUP rufe ich dann mit 8 auf?!

Benutzeravatar
Panulli
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 110
Registriert: 20. Apr 2005 07:20

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von Panulli »

Telefonjoker hat geschrieben:hmm kommt nicht mehr...???

Dann nochmal:

Also, wenn ich einen Knoten x lösche und an dessen Stelle den Knoten y setze, dann nimmt y seine Farbe mit.
Wenn x schwarz war und y rot, dann ist nach dem Ersetzen y immer noch rot.

Stimmt's?

Was ich mich jetzt noch frage ist, was passiert, wenn der Elternknoten von x auch rot war?
Dann ist das neue Kind y vom Elternknoten auch rot; was ja nicht sein darf.
Was passiert jetzt? DeleteFIXUP wird ja nicht aufgerufen...

Wenn deine zu löschender Knoten x zwei Kinder hat, dann ist y der zahlenmäßige Nachfolger (Kleinster Eintrag im rechten Teilbaum von x). Da in diesem Fall x!=y werden die Daten von y nach x kopiert. NUR die Daten, NICHT die Farbe. Das bedeutet zeichnerisch, dass Knoten x mit dem Zahlenwert von y überschrieben wird und der Knoten y wegfällt. Es werden hier, wie schon erwähnte keine Farben verändert!

Korrigiert mich, aber so sollte es sein.
Grüßlich ULI

http://www.SGE4ever.de

Benutzeravatar
Panulli
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 110
Registriert: 20. Apr 2005 07:20

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von Panulli »

Telefonjoker hat geschrieben:also, wenn in Übung 12 G1 zuerst den Knoten 12 löschen wurde; dann hätte ich von der Wurzel den Pfad 38schwarz -> 19rot -> 8schwarz. Richtig?
Und FIXUP rufe ich dann mit 8 auf?!

Nein, die 8 ist nicht schwarz. Hier hat die 12 nur EIN Kind, dann ist der zu löschende Knoten (x) auch y. Da in diesem Fall x=y (siehe Algo, Zeile 13), werden KEINE Daten kopiert, sondern nur der Sohn von x an die Stelle von x verschoben wird. Somit bleibt die 8 rot.
Grüßlich ULI

http://www.SGE4ever.de

Telefonjoker
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 19. Apr 2008 21:02

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von Telefonjoker »

hi Uli,

aber dann habe ich in dem Fall ja zwei rote Knoten hintereinanderder. Das Kind von der roten 19 ist die rote 8.
Das darf aber nicht sein. Wie korrigiere ich das?
Zuletzt geändert von Telefonjoker am 24. Sep 2008 15:24, insgesamt 1-mal geändert.

xilef
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Jan 2008 04:47

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von xilef »

Hi,

nachdem du einen inneren Knoten gelöscht hast, ist jetzt die Farbe des Knotens relevant, der an der Stelle deines ersetzenden Knotens steht. Diese müsste schwarz sein. Also wird RB-FIXUP aufgerufen und du musst einen der Fälle 1-4 ausführen. Ich habe das Beispiel noch nicht nachgestellt und kann dir daher leider nichts genaueres sagen.

Bitte korrigiert mich wenn ich falsch liege.

xilef

Telefonjoker
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 19. Apr 2008 21:02

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von Telefonjoker »

ah, ok, jetzt hab ich's.

Also, die 8 rückt an die Stelle von der 12; und da die 12 schwarz war, wird FIXUP aufgerufen und die 8 schwarz gefärbt.

xilef
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Jan 2008 04:47

Re: Frage zu Übung 12 (Rot-Schwarz Bäume)

Beitrag von xilef »

Ja,

und nach Zeile 23 wird die 8 dann einfach schwarz gefärbt. Also die While-Bedinung ist nicht mehr gegeben und somit springt der Algo einfach in die Zeile 23...

Ich hoff ich raf das bald mal... :roll:

Antworten

Zurück zu „Archiv“