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

[ChristianK]

In der Übung 12 Aufgabe 1 (Löschen aus Rot-Schwarz Bäumen) haben wir zum Spaß mal versucht aus dem Ausgangsbaum den Knoten 19 zu löschen. Das funktioniert aber irgendwie nicht so richtig... Weiß jemand bescheid, wie das geht??

[Tigger]

Also als erstes wird 19 entfernt und mit der schwarzen 31 ersetzt. Jetzt wird FixUp mit dem rechten schwarzen NIL von 31 aufgerufen. Jetzt kommt die Falle: Die im Buch/Script angegebenen Fälle gelten ja nur für die Brüder w die rechte Kinder sind. Das wird ja in Codezeile 3 vom Delete-Fixup abgefragt. Ensprechend geht es dann weiter mit Codezeile 22 also die gleiche Fälle nur mit "rechts" und "links" vertauscht. Bei unserem Beispiel haben wir dann Fall 4, also der Bruder (12, welcher ein linkes Kind ist, also vertauschte Fälle benutzen!) ist schwarz und sein linkes (nicht rechtes, da ja jetzt vertauscht) Kind ist rot. Also tauschen 8 und 12 die Farben und es wird eine Rechtrotation (anstatt Linksrotation) ausgeführt. Damit ist die rote 12 nun der Vater der beiden schwarzen Kinder 8 und 31.

Soweit sogut. Ab jetzt bin ich mir auch nichtmehr sicher... Delete-Fixup müsste jetzt auf die 31 angewendet werden. Wir hatten ja die rote 19 mit der schwarzen 31 ersetzt, also müsste die Farbe der 31 jetzt Rot-Schwarz sein (korrigiert mich wenn ich falsch liege). Dann käme jetzt Fall 2 zum Zuge mit 8 als schwarzem Bruder und seinen beiden schwarzen NIL-Kindern. Laut definition wird jetzt ein schwarz von 31 entfernt, womit der Knoten rot wäre, und die 8 wird auch einfach rot gefärbt. Dann würde Delete-FixUp auf den Vater von 31 angewand, also auf 12. Da 12 ja rot ist, terminiert die schleife und die 12 wird schwarz.

Wie gesagt beim letzten Teil bin ich mir nicht wirklich sicher. Hätte da gerne auch nochma ein Feedback

[ChristianK]

Ahja... ich wusste nicht, dass man auch Left-/Right Rotation vertauschen muss... weil da steht ja nur "rechts" und "links" vertauschen...
Gut dann funktioniert das... Allerdings komme ich dann gleich zu Fall 4, denn der Bruder w (12) von x (NIL) ist schwarz und das linke Kind von w (8) ist rot. Vielleicht hast du das auch genau so gemeint? Jedenfall kommt ein korrekter Rot-Schwarz Baum raus, wenn man Fall4 mit vertauschtem rechts/links und Left/Right Rotate anwendet

Also ich denke man muss sowohl rechts/links als auch right/left Rotation vertauschen und dann ganz normal die Fälle anwenden (hier lediglich Fall4 und dann ist man fertig). Kann das jemand so bestätigen?

[Tigger]

Allerdings komme ich dann gleich zu Fall 4, denn der Bruder w (12) von x (NIL) ist schwarz und das linke Kind von w (8) ist rot. Vielleicht hast du das auch genau so gemeint?

Jepp, is auch schon korrigiert

Jedenfall kommt ein korrekter Rot-Schwarz Baum raus, wenn man Fall4 mit vertauschtem rechts/links und Left/Right Rotate anwendet

Auch dass stimmt, allerdings glaube ich, dass das noch nicht reicht. Die Schleife muss ja terminieren und das tut sie meiner Ansicht nach noch nicht, auch wenn der Baum schon formal korrekt ist. Die Schleife muss ja entweder die Wurzel oder einen roten Knoten erreichen und ihn schwarz färben, was sie ja bis jetzt noch nicht getan hat.

[levitin]

Tigger, sei mal bitte so nett und mach mal deinen "merry fellow" aus jeder Nachricht weg.. stört sehr zu lesen. Danke für dein Verständnis ))

[mba]

Also als erstes wird 19 entfernt und mit der schwarzen 31 ersetzt. Jetzt wird FixUp mit dem rechten schwarzen NIL

FALSCH!

Das entfernen eines roten Knotens führt nie dazu, dass die Methode RB-DELETE-FIXUP(T,x) aufgerufen wird siehe Zeile 16 in RB-DELETE(T,z).

Den Nachfolger von 19 suchen, dies wäre die 31. Diesen Knoten löschen mit 19 ersetzen und rot färben.

Ähnliche Fällte kann man gut in einem Applet nachvollziehen.
http://fbim.fh-regensburg.de/~saj39122/ ... start.html

[Tigger]

Argh, stimmt. Hatte versehentlich den Schlüssel mit der Farbe assoziiert. In dem Fall is es ja dann ganz einfach. Naja mein Baum war wenigstens schöner balanciert, auch wenn er Falsch war .
B.t.w. es bleibt doch trotzdem dabei, dass beim benutzen der "vertauschten Fälle" sich auch die Rotate-Richtungen ändern, oder?

[mba]

B.t.w. es bleibt doch trotzdem dabei, dass beim benutzen der "vertauschten Fälle" sich auch die Rotate-Richtungen ändern, oder?

Ja, alles "RECHTS" wird zu "LINKS" und andersrum. Dies gilt auch für das RECHTS / LINKS rotieren.

[ChristianK]

Auch dass stimmt, allerdings glaube ich, dass das noch nicht reicht. Die Schleife muss ja terminieren und das tut sie meiner Ansicht nach noch nicht, auch wenn der Baum schon formal korrekt ist. Die Schleife muss ja entweder die Wurzel oder einen roten Knoten erreichen und ihn schwarz färben, was sie ja bis jetzt noch nicht getan hat.

Doch das terminiert wunderbar: Weil am Ende von Fall 4 wird x=Wurzel von dem Baum gesetzt und damit springt er aus der Schleife

[Tigger]

Weil am Ende von Fall 4 wird x=Wurzel von dem Baum gesetzt und damit springt er aus der Schleife

Jo jetzt seh ichs auch. Die haben sich im Buch etwas ungünstig ausgedrückt

[ChristianK]

Also als erstes wird 19 entfernt und mit der schwarzen 31 ersetzt. Jetzt wird FixUp mit dem rechten schwarzen NIL

FALSCH!

Das entfernen eines roten Knotens führt nie dazu, dass die Methode RB-DELETE-FIXUP(T,x) aufgerufen wird siehe Zeile 16 in RB-DELETE(T,z).

Den Nachfolger von 19 suchen, dies wäre die 31. Diesen Knoten löschen mit 19 ersetzen und rot färben.

Ähnliche Fällte kann man gut in einem Applet nachvollziehen.
http://fbim.fh-regensburg.de/~saj39122/ ... start.html

Mag sein, dass das Applet das so sagt und der Baum, der dann rauskommt ist auch korrekt, aber wenn man sich den Code im Buch anschaut muss die Fixup Funktion aufgerufen werden, denn diese wird aufgerufen, wenn y schwarz ist. Dem y wird im Code ganz oben der Nachfolger (31) zugewiesen. Danach ändert sich das y nicht mehr auch wenn es an die Position der 19 kopiert wird. Die Farbe von y selbst bleibt aber schwarz und somit muss auch FIXUP aufgerufen werden, wo man dann einmalig Fall4 anwendet und rechts/links usw. vertauscht. Vielleicht gibt es da verschiedene Codes, denn beide Lösungen ergeben einen korrekten RS Baum, aber nach dem Code aus dem Buch muss Fixup aufgerufen werden oder nicht?

[Tigger]

Sehe ich (jetzt) nicht (mehr) so Es ändert sich zwar y nicht mehr, aber der Schlüssel und die Satelitendaten von z werden einfach mit denen von y ersetzt (Zeile 14 +15). Also wird y nicht wirklich verschoben, sondern nur seine Daten und anschließend verschwindet er einfach. Genau darüber bin ich ja auch vorhin gestolpert

[mba]

Mag sein, dass das Applet das so sagt und der Baum, der dann rauskommt ist auch korrekt, aber wenn man sich den Code im Buch anschaut muss die Fixup Funktion aufgerufen werden, denn diese wird aufgerufen, wenn y schwarz ist. Dem y wird im Code ganz oben der Nachfolger (31) zugewiesen. Danach ändert sich das y nicht mehr auch wenn es an die Position der 19 kopiert wird. Die Farbe von y selbst bleibt aber schwarz und somit muss auch FIXUP aufgerufen werden, wo man dann einmalig Fall4 anwendet und rechts/links usw. vertauscht. Vielleicht gibt es da verschiedene Codes, denn beide Lösungen ergeben einen korrekten RS Baum, aber nach dem Code aus dem Buch muss Fixup aufgerufen werden oder nicht?

FALSCH!

Zeile 16: if farbe[y]= SCHWARZ
Zeile 17: then RB-DELETE-FIXUP(T,x)

y ist den Knoten der gelöscht werden soll. Dieser wird auch von der Methode RB-DELETE(T,z) zurückgegeben. Wir fixen nur dann, wenn der zu löschende Knoten schwarz ist. Siehe Buch Seite 289 warum wir nur schwarze Knoten (die gelöscht werden) fixen.

Y ist eindeutig der Knoten, der gelöscht wird.

[ChristianK]

klar wird das y (31) und der damit verknüpfte Inhalt an die Position der 19 kopiert, aber das y selbst wird doch nur ein einziges mal zugewiesen und bleibt doch trotzdem der schwarze Knoten (der dann gelöscht wird). Oder wird die Farbe der schwarzen 31 dadurch rot, dass ich den Inhalt in die rote 19 KOPIERE? Anstelle der 19 steht dann die 31 und das ist ein roter Knoten... das ist klar. Aber dadurch verändert sich ja nicht das y... y ist weiterhin ein Zeiger auf den vom Baum getrennten schwarzen Knoten 31 und die Abfrage in Zeile 16 bezieht sich nunmal auf das y und nicht auf den Inhalt vom y der in die rote 31 kopiert wurde...

[Tigger]

Hmm, das is allerdings ein Argument. Tatsächlich sagt mba ja das wir FixUp nur ausführen, wenn y, der zu löschene Knoten schwarz ist. Da aber y als TreeSuccessor definiert ist und der un unserem Falle 31 ist also SCHWARZ, müsste man fixup ausführen.