[DSAL] Rot-Schwarz-Bäume

[House]

Also folgendes Bild:


Ich möchte die 5 löschen
nach vorlesungsfolien:

Wie bei normalen binären Suchbäumen
wird der Knoten entweder direkt gelöscht
oder sein Successor wird gelöscht und
überschreibt den eigentlichen Knoten

Aber meiner Ansicht nach geht beides nicht...

[thana]

klar geht das.
Aber danach muss die rotschwarz bedingung wiederhergestellt werden.

[Cornflake]

Falls es noch wen interressiert:

Mit dem Succsessor ist EIN Nachfolger gemeint, in diesem Falle die 3, und nicht die 7.

Du sollst also einen Nachfolger an Stelle der 5 schreiben, also holst du die 3 in den Knoten der 5 und löschst die 3.
Nachdem du dann mit Hilfe der schwarzen Marke den schwarz-roten Knoten (3) schwarz eingefärbt hast bist du auch schon wieder fertig mit löschen der 5.

[aRo]

ähm, Cornflake, vielleicht ist das etwas unverständlich.

Ich beschäftige mich auch gerade mit den lieben Rot-Schwarz Bäumen. Das Einfügen ist soweit nicht so schwer, und das kann ich auch.
Aber beim Löschen funktionierts noch nicht so recht.

Mit dem Nachfolger ist meiner Meinung nach nämlich durchaus DER Nachfolger gemeint. Es ist nur so, dass das nur angewendet wird, wenn der zu löschende Knoten ZWEI Kinder hat.
Hat er keine -> wunderbar, einfach löschen.
Hat er eins, dann kann er einfach ausgeschnitten werden und das eine Kind wird hochgeschoben, wie hier.

Danach müssen die Rot-Schwarz Bedinungen wieder erfüllt werden.

Ich verstehe das mit der Marke immer noch nicht recht, denn irgendwie passt das nicht. Vielleicht haben wir es auch mal im Tutorium falsch gemacht.
Also, wer genau kriegt die Marke?

Im Cormen verstehe ich es so:
Wir bestimmen einen Knoten y, der ausgeschnitten wird. Entweder ist das unser zu löschender Knoten z selbst (wenn z höchstens ein Kind hat) oder es ist zs Nachfolger (Sucessor).

So, dann kriegt der folgende Knoten die Marke:
Entweder ys einziges Kind, sofern er eins hatte, oder das NIL an y, wenn y kein "richtiges" Kind hatte.

Betrachtet bitte einmal diesen Rot-Schwarz Baum:

Wenn ich hier die 3 löschen möchte, dann hat die 3 2 Kinder, ich bestimme also den Nachfolger, das ist die 4.

D.h. y=4 und hat keine Kinder, das hieße nun eigentlich, dass die 3 durch die 4 ersetzt wird und die schwarze Marke da liegen bleibt, wo die 4 war.
Dann müssten wir mit den Fällen anfangen, wenn ich das richtig sehe (schwarzer Bruder und so)

Im Tutorium haben wir es nun so gemacht:
Wir haben die 4 richtig hochkopiert und dann behauptet die Marke würde nun auf dieser Stelle, wo jetzt die 4 ist, liegen, so dass wir diese einfach schwarz färben können. Aber so lese ich das keinesfalls aus den Folien oder dem Cormen.

Wie ist es nun richtig?

Und, ganz WICHTIG:
Kennt jemand ein Java Applet, das beim Löschen genau so arbeitet wie wir, das also immer den Nachfolger nimmt und niemals den Vorgänger?? Wär sehr cool zum Üben!!

Danke!

[Rex69]

Ich weiss jetzt nicht direkt, wie ihr die Rot-Schwarz Bäume in der Vorlesung gesehen habt, aber hier gibts ein nettes Applet wo man verschiedene Baum-Datenstrukturen einstellen kann, unter anderem Rot-Schwarz.
Vielleicht hilft es ja.
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

[aRo]

hallo Rex69.

Das Applet ist zwar auch schön, macht es aber leider auch anders.

Folgendes Skript arbeitet so wie wir:
http://people.ksp.sk/~kuko/bak/index.html

(glaube ich zumindest, jedenfalls sucht es wenigstens immer den Successor)

Schade ist jetzt allerdings, dass das Applet die 3 in dem von mir geposteten Baum so löscht, wie wir im Tutorium. Das heißt, die Marke der 3 kommt irgendwie zu der 4, und das verstehe ich wie gesagt nicht.

Wär cool, wenn mir das mal jemand erklären könnte - irgendwer muss doch hier in RS-Bäumen löschen können

[NeX]

D.h. y=4 und hat keine Kinder, das hieße nun eigentlich, dass die 3 durch die 4 ersetzt wird und die schwarze Marke da liegen bleibt, wo die 4 war.
Dann müssten wir mit den Fällen anfangen, wenn ich das richtig sehe (schwarzer Bruder und so)

Ja das ist richtig.

Man löscht in einem Baum ja meist rekusiv. D.h. ich suche den Nachfolger (bei 2 Kindern) und nehme diesen an die Stelle des Knotens den ich löschen will.
D.h. des Nachfolger Knoten muss gelöscht werden.
--> Rekursiv.

Am Ende ist die Marke an dem Punkt des wirklich gelöschten Knotens.

In diesem Fall bedeutet das:

--4 anstelle von 3 (Farbe von 3 wird beibehalten).

--Da schlussendlich die 4 gelöscht wurde, die ein rotes Blatt ist. passiert gar nichts mehr, da alle Konsistenzregeln erfüllt sind.

so lösche ich zumindest und es klappt erstaunlich gut

Im Tutorium haben wir es nun so gemacht:
Wir haben die 4 richtig hochkopiert und dann behauptet die Marke würde nun auf dieser Stelle, wo jetzt die 4 ist, liegen, so dass wir diese einfach schwarz färben können. Aber so lese ich das keinesfalls aus den Folien

kommt auf das gleiche von oben heraus...der ansatz ist aber falsch...ich habe aber auch gehört das viele Tutoren RS-Bäume gar nicht kannten vorher (bzw nicht so können mussten) und somit auch nicht sicher im Umgang mit ihnen sind

zum applet:
ich arbeite auch mit diesem applet und stelle keine unterschiede fest zu dem was wir gemacht haben....

es eignet sich super zum lernen, da es auch Random-Zahlen einfügen kann, so dass man nicht immer selber was suchen muss....
(einfach ohne eine Zahl ins Kästchen zu schreiben >Insert< machen)

ich hoffe ich konnte dir helfen

[Cornflake]

ähm, Cornflake, vielleicht ist das etwas unverständlich.

Mit dem Nachfolger ist meiner Meinung nach nämlich durchaus DER Nachfolger gemeint. Es ist nur so, dass das nur angewendet wird, wenn der zu löschende Knoten ZWEI Kinder hat.
Hat er keine -> wunderbar, einfach löschen.
Hat er eins, dann kann er einfach ausgeschnitten werden und das eine Kind wird hochgeschoben, wie hier.

Das ist ganz gut zusammengefasst finde ich. Außer dem Punkt mit einem Kind.

Also, hat er EIN Kind, kann man sagen, dass der Nachfolger reingeschrieben werden wird und rekursiv wird weiter gelöscht. Hat der zu löschende Knoten jedoch keinen Nachfolger, sonder lediglich einen Vorgänger, so wird der Vorgänger reingeschrieben und rekursiv weiter...

Also kurz:
Keine Nachfolger: Knoten löschen; Marke steht an der Stelle.
2 Nachfolger: Nachfolger löschen; rekursiv weiter; Marke an Stelle des später eigentlich gelöschten Knotens.
1 Nachfolger: Pimär Nachfolger löschen, sonst Vorgänger; rekursiv weiter.

[aRo]

hallo!

Ah, NeX, du hast recht!

Weil der tatsächlich gelöschte Knoten die 4 ist, und diese rot ist, wird "Delete-Fixup" gar nicht aufgerufen, sondern nur die Daten kopiert!

Danke dir!

Aber sonst müsste die Marke wirklich immer bei dem ausgeschnittenen Knoten liegen (also nicht zwangsläufig unser zu löschender Knoten z) bzw. dessen einziges Kind.
Zumindest steht das im Cormen so.

@Cornflake:
Das widerspricht dem Cormen. Ich schaue mir das jetzt nochmal genau an!i

Danke euch zwei!

Achso, ja:
Kennt jemand ein Applet für BBäume, das mit Onepass arbeitet?


EDIT:

Ich habe mir nochmal mit Martin Habbecke unterhalten und er hat nochmal in der google Group geschrieben.
Ich habs jetzt verstanden

Wir machen es wohl zum Glück wirklich so, wies im Cormen steht.
Ich denk ich kanns jetzt also, muss mir nur noch irgendwie die Fälle reinkloppen.

Dankeschön!

[LonliLokli]

Ist der bei uns definierte Fall 4 ein terminal Fall (dh nach diesem Schritt ist man mit Wiederherstellugn der RS - Bediengung fetig )?

[Commo]

Das im Cormen ist doch auch intuitiver, oder nicht? Zumindest, wenn man etwas anderen Sprech benutzt: Wenn ich einen Knoten x _entferne_, kann ich eine Konsistenzbedingung verletzen. Wenn ich beim löschen x nicht _entferne_ sondern durch einen Knoten y _ersetze_, kriegt y einfach die Farbe von x und farbtechnisch ist dort alles im Lot. Tatsächlich haben wir dann aber y _entfernt_.