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

ChristianK
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 127
Registriert: 13. Sep 2007 01:15
Wohnort: Darmstadt
Kontaktdaten:

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

Beitrag von ChristianK »

ja so sehe ich das auch
mba betrachtet den roten Knoten mit dem Inhalt von y als y selbst, aber das ist nur eine Kopie von y. Der eigentliche y Knoten ist der schwarze Knoten, sodass FIXUP aufgerufen werden muss...

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

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

Beitrag von Tigger »

Der Begriff des "zu Löschenden Knotens" wird hier etwas waage behandelt. Man kann ihn nämlich als eigentlich zu löschenden Knoten (z) interpretieren, oder als den Nachfolger (y), der dann im endeffekt wiklich zu löschen ist, nachdem seine Daten in z kopiert wurden. Wenn es sich beim Nachfolger um einen roten Knoten handelt, dann hat mba ja ganz recht, dass FixUp nicht ausgeführt werden muss.

Dann wäre ja eigentlich auch die Musterlösung von Übungsblatt 12 falsch. Denn da wird ja auch Knoten 19 durch die 31 ersetzt, aber erst durch den Fixup schwarz gefärbt. Nach unserer Überlegung dürfte FixUp ja nichtmal aufgerufen werden, sondern durch dass Kopieren ädert sich ja die Farbe des Knoten 19->31 garnicht.

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

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

Beitrag von s!mon »

Ich habe hier ein Java-Applet gefunden:

http://fbim.fh-regensburg.de/~saj39122/ ... start.html

Ich weiß nicht ob es bei RSB Unterschiede in den Algorithmen gibt, mir sind bei diesem Applet bisher keine aufgefallen. Das ist zum Üben denke ich mal ganz cool, vor allem weil es ja nur wenige Übungen bei uns gibt obwohl es imo (vom Algorithmus ausführen her) das schwerste Thema is das wir hatten.

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

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

Beitrag von Tigger »

Das Applet hat auch schon mba gepostet. Das Problem ist, dass es wohl leicht abweichende Definitionen des B-Baums gibt. Deswegen würde ich mich nicht auf externe Quellen beziehen. Bei dem Applet kommt zwar sicherlich auch ein gültiger B-Baum raus, aber wie unser Beispiel heute gezeigt hat, gibts dann doch noch unterschiede. mba's Baum ist ja auch nach Definition korrekt, aber der Algorithmus so wie ChristianK und ich ihn ausgeführt haben, hat ihn nochmal in der Höhe verkürzt.

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

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

Beitrag von s!mon »

Ah ok, dann sorry. Ich hatte mir nur das Einfügen kurz angeschaut und das erschien mir gleich zu sein.

PS: Du meintest wohl RSB oder ;)

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

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

Beitrag von Tigger »

s!mon hat geschrieben:PS: Du meintest wohl RSB oder ;)
Argh, heut habb ichs aber.... :oops: Natürlich RSB

Benutzeravatar
mba
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 13. Jul 2007 19:16

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

Beitrag von mba »

Irgendwie ist das verwirrend z.B. in der Lösung zu dieser Übung, löschen wir den Knoten 8, y hat den Schlüssel 8 und ist rot, deswegen rufen wir FIXUP nicht auf. Daraus schließe ich, dass y immer der zu löschende Knoten ist, den wir auch überprüfen ob dieser schwarz ist. Analog werden alle anderen Knoten gelöscht und immer ist y der zu löschende Knoten.

Es kann jedoch sein, dass wenn der zu löschende Knoten zwei Kinder hat, dass dann y zum Nachfolger des zu löschenden Knotens wird, wie es in Zeile 3 steht. Deswegen würden wir dann den Nachfolger des zu löschenden Knotens überprüfen.

Komisch, dass solch ein Fall nie in der Übung behandelt wurde.
»Es ist noch kein Meister vom Himmel gefallen«
Wenn doch, wär er jetzt tot.
Bild

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

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

Beitrag von Tigger »

mba hat geschrieben:Komisch, dass solch ein Fall nie in der Übung behandelt wurde.
Wurde indirekt schon, wie ich oben schon geschrieben habe. Denn der Knoten 19 wird ja auch in der Übung entfernt. Da er aber da schon keine Kinder mehr hat, war es dann für das Ergebnis egal. Aber die Begründung in der Musterlösung, dass der Knoten 31 durch FixUp schwarz gefärbt wird, halte ich für falsch. Gibts denn nochmal Sprechstunden vor den Klausuren? Hätte da nämlich gerne nochmal ne offizielle Erklärung.

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 »

Wenn ich mir den Pseudocode von RB-DELETE so ansehe, müsste beim Löschen der 8 eigentlich key[y] = 8 und x = left[y] = NIL[T] sein (Zeile 5). Damit kann man aber sinnvollerweise kein Fixup aufrufen, da w auch wieder ein NIL-Knoten ist. Spätestens wenn Fixup dann versucht, auf left [NIL [T]] bzw. right [NIL [T]] zuzugreifen (Zeile 9), gibt es ein richtiges Problem.

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

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

Beitrag von Tigger »

In diesem Fall wird auch wirklich kein FixUp aufgerufen, weil der zu löschende Knoten 8 keine (nichtNIL) Kinder hat. Damit ist er auch der Knoten der dann im endeffekt wirklich gelöscht wird (er wird nicht einfach von einem Kind ersetzt). Also ist y=8 (Zeile 2) und da die 8 ja rot ist wird kein FixUp aufgerufen (Zeile 16). Nochmal ganz klar: Die Aussage, das FixUp nicht aufgerufen wird wenn der zu löschende Knotenr rot ist, ist prinzipiell korrekt, WENN mit zu löschender Knoten wirklich der Knoten gemeint ist, der am Ende gelöscht wird und nicht der der ersetzt wird (das ist ja der Fall wenn der der Knoten der zum löschen an die DeleteFunktion übergeben wurde ein innerer Knoten ist).
Oder als Faustregel:
- Ist der zu löschende Knoten ein Blatt, zählt dessen Farbe als FixUp Kriterium
- Ist der zu löschende Knoten ein inner Knoten, zählt die ursprüngliche Farbe des Knotens, der ihn ersetzt als FixUp Kriterium

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

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

Beitrag von Telefonjoker »

Ich zitiere aus den Buchmannfolien:
Sollte die Farbe des entfernten Knotens rot gewesen sein, sind die RS Eigenschaften nach seiner Entfernung immer noch erfüllt.
- da ein roter Knoten entfernt wurde, wurde keine schwarze Höhe verändert.
[...]
Ist das denn richtig?

RB-Deleto(T,z) setzt ja ein y mit dem Nachfolgerknoten. Und erst dann am Ende wird gefragt, ob farbe[y] = schwarz ist und evtl FIXUP aufgerufen. :roll:

Und wenn ich einen roten Knoten lösche und durch einen schwarzen ersetze, habe ich doch eine andere Schwarzhöhe, oder?
Zuletzt geändert von Telefonjoker am 23. Sep 2008 22:51, insgesamt 2-mal geändert.

Benutzeravatar
bender
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 7. Apr 2008 20:20

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

Beitrag von bender »

Das siehst du richtig.

Die Aussage von Buchmann stimmt nur, wenn der Nachfolgerknoten auch rot war.

Im Pseudocode wird y der TREE-SUCCESSOR(z) zugewiesen (Zeile 3).

Und Fixup wird dann aufgerufen, wenn der Nachfolger schwarz war.

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

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

Beitrag von Telefonjoker »

Was ist eigentlich, wenn ich einen schwarzen Knoten lösche und durch einen roten Vorgänger ersetze?
Dann können ja zwei rote Knoten hintereinander auf einem Pfad auftreten.

Aber Deleto-FixUP wird nur aufgerufen, wenn der Nachfolgeknoten schwarz ist...

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

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

Beitrag von Tigger »

Wenn der innerer Knoten y beim löschen durch einen Nachfolger ersetzt wird, ändert sich die Farbe von y nicht. Es werden nur der Schlüssel und die Satelitendaten ersetzt. Wenn das Kind (nachfolger von x), welches ja dann gelöscht ist, rot war, sind wir fertig. Wenn es schwarz war, müssen wir FixUp aufrufen.

michael2k5
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 2. Dez 2005 19:22
Wohnort: Darmstadt-Eberstadt
Kontaktdaten:

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

Beitrag von michael2k5 »

Telefonjoker hat geschrieben:Ich zitiere aus den Buchmannfolien:
Sollte die Farbe des entfernten Knotens rot gewesen sein, sind die RS Eigenschaften nach seiner Entfernung immer noch erfüllt.
- da ein roter Knoten entfernt wurde, wurde keine schwarze Höhe verändert.
[...]
?
also die aussage ist IMO schon richtig. hier ist nur etwas unklar, was mit "entfernter knoten" gemeint ist. folgende fälle können auftreten:
(1) wenn wir einen inneren knoten löschen sollen mit 2 kindern, dann wird ja nicht der innere knoten entfernt, sondern sein nachfolger.
(2) wenn wir einen inneren knoten löschen sollen mit einem kind, dann wird der knoten ausgeschnitten und tatsächlich entfernt.

wenn das die defintion von "entfernter knoten" ist, dann ist die aussage richtig und ein entfernter knoten, der rot ist, ist immer ohne fixup zu entfernen.
wenn mit "entfernter knoten" "zu löschender knoten" gemeint ist, dann nur, sofern der tatsächlich entfernte knoten auch rot ist (was IMO aber keinen sinn machen würde)

Antworten

Zurück zu „Archiv“