

Jepp, is auch schon korrigiertChristianK hat geschrieben: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?
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.ChristianK hat geschrieben:Jedenfall kommt ein korrekter Rot-Schwarz Baum raus, wenn man Fall4 mit vertauschtem rechts/links und Left/Right Rotate anwendet
FALSCH!Also als erstes wird 19 entfernt und mit der schwarzen 31 ersetzt. Jetzt wird FixUp mit dem rechten schwarzen NIL
Tigger hat geschrieben: B.t.w. es bleibt doch trotzdem dabei, dass beim benutzen der "vertauschten Fälle" sich auch die Rotate-Richtungen ändern, oder?
Doch das terminiert wunderbar: Weil am Ende von Fall 4 wird x=Wurzel von dem Baum gesetzt und damit springt er aus der SchleifeAuch 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.
Jo jetzt seh ichs auch. Die haben sich im Buch etwas ungünstig ausgedrücktChristianK hat geschrieben:Weil am Ende von Fall 4 wird x=Wurzel von dem Baum gesetzt und damit springt er aus der Schleife
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?mba hat geschrieben:FALSCH!Also als erstes wird 19 entfernt und mit der schwarzen 31 ersetzt. Jetzt wird FixUp mit dem rechten schwarzen NIL
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
FALSCH!ChristianK hat geschrieben: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?