PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Einfügen in einen Rot-Schwarz-Baum


Senior Sanchez
2007-05-15, 21:18:48
Hi,

Ja, das Thema musste ja mal kommen und nun ist es da: Mein "Lieblingsthema": Rot-Schwarz-Bäume.
Zur Visualisierung hilft vllt das hier: http://fbim.fh-regensburg.de/~saj39122/gikasch/applet.html

Nun aber zum Thema:

Allgemein ist mir das klar wie das abläuft. Füge ich einen neuen Knoten ein, so wird er als Blatt angehangen und rot gefärbt (ist natürlich der Baum noch leer wird der Knoten als Wurzel reingehangen und schwarz gefärbt).

An der Stelle des neuen Knoten prüfe ich nun dessen Vater und Großvater auf die Farbe. Ist der Vater rot, der Großvater schwarz und der Onkel auch rot, so kann ich einfach umfärben.
Ist der Vater dagegen rot, der Großvater rot oder schwarz, so muss ich eine Rotation durchführen.

Bis dahin ist alles klar. Aber wie gehe ich nun vor, wenn nach der Rotation noch eine Umfärbung oder vllt eine weitere Rotation erfolgen muss? Ich kann mir das ehrlich gesagt noch nicht erklären.

Als Beispiel kann man bei dem Applet mal in folgender Reihenfolge Knoten einfügen: 20 10 30 40 50. Bei 50 muss er rotieren und 40 wird der Parent von 30 und 50. Aber nach welchem Schema erfolgt jetzt die Umfärbung?

Ich muss das ja irgendwie allgemein formulieren können, dass heißt Regeln, wonach ich erkenne, dass ich dann dieses und jenes machen muss.

Schonmal vielen Dank und ich hoffe, jemand weiß weiter.

AtTheDriveIn
2007-05-15, 22:35:20
Wenn ich dein Problem jetzt richtig verstanden habe, folgende Antwort:

Man prüft solange auf die Rot-Schwarz Bedingungen bis der zu untersuchende Knoten keinen Vater hat, also die Wurzel ist.


Der Wikipedia Artikel zum Rot-Schwarz-Baum ist ziehmlich ausführlich

Senior Sanchez
2007-05-16, 11:20:26
Ja, das ist klar.

Es geht mir um folgendes:


20 (black)
10(black) 30(black)
40(red)
50(red)


Man sieht das die rot-Bedingung verletzt ist bei 40 und 50. Also wird beim Parent (30) nachgeschaut ob er schwarz ist und nur rote Kinder hat. Schwarz ist er, aber er hat im linken Ast einen NIL-Knoten, der per Definition schwarz ist.
Deshalb wird jetzt eine Rotation durchgeführt.


20 (black)
10(black) 40(red)
30(b) 50(red)

Nun verstehe ich aber nicht, nach welcher Regel jetzt weiterverfahren wird. Er färbt im Applet die 40 jetzt schwarz und die 30 rot, aber nach welcher Regel? (Warum er was tun muss, ist klar, aber ich weiß nicht wie er jetzt darauf kommt das er umfärbt und nicht noch weiter rotiert oder so.)

Gast
2007-05-16, 13:31:17
vorher:

20 (black)
10(black) 40(red)
30(b) 50(red)


nachher:

20 (black)
10(black) 40(red)
30(black) 50(black)


woraus die regel hervorgeht:
ist ein knoten rot, dann sind seine beiden kinder schwarz.

Gast
2007-05-16, 13:37:02
oder meintest du diesen schritt?

Jeder Pfad, von einem gegebenen Knoten zu seinen Blattknoten, enthält die gleiche Anzahl schwarzer Knoten (Schwarzhöhe/Schwarztiefe).

das sind einfach die regeln. ohne die kommst du nicht weiter. das sind 5 stück die muss man umsetzen und das wars.

Senior Sanchez
2007-05-16, 14:10:44
oder meintest du diesen schritt?

Jeder Pfad, von einem gegebenen Knoten zu seinen Blattknoten, enthält die gleiche Anzahl schwarzer Knoten (Schwarzhöhe/Schwarztiefe).

das sind einfach die regeln. ohne die kommst du nicht weiter. das sind 5 stück die muss man umsetzen und das wars.

Ja, das ist mir klar.
Die Bedingungen kenne ich.

Es geht nur darum, wie ich jetzt darauf komme dort diese beiden Knoten umfärben zu müssen - und nicht zum beispiel rotieren muss.

Nasenbaer
2007-05-19, 14:57:48
Ich würd mir dazu am besten ein Buch aus der örtlichen Uni Bibliothek holen (in "Algorithmen" von Cormen sollte was dazu stehen), denn es gibt dort etliche Fälle und auch Professoren haben da schonmal nen Fall übersehen. Deswegen würd ich auch nicht unbedingt auf Wikipedia vertrauen, da RB-Trees sehr kniffelig sind.

Gast
2007-05-19, 16:50:16
lad dir einfach das applet, vielleicht kommst du so an den code X-D

Coda
2007-05-19, 17:59:13
Ja, RB-Trees sind echt ein Unding. Ich hasse es...

Ich hab bis heute nicht verstanden wie man auf sowas kommt X-D

Nasenbaer
2007-05-20, 08:52:49
Ja, RB-Trees sind echt ein Unding. Ich hasse es...

Ich hab bis heute nicht verstanden wie man auf sowas kommt X-D
Naja schlecht sind sie ja nicht. Maximal 2 Rotationen (d.h. wenig Daten zu kopieren) und dazu einen sehr gut balancierten Baum. AVL-Bäume brauchen AFAIR log( n ) Rotationen im Extremfall und sind auch nur minimal besser balanciert.
Stimmt aber schon wie man auf solche Algorithmen kommt will ich besser auch nicht wissen. :D

Senior Sanchez
2007-05-20, 09:42:45
Naja, die Grundidee hinter Red-Black-Trees ist ja ganz einfach: einen 2-3-4-Baum auf einen binären Baum abzubilden. Aber alles was danach kommt, puuuh, da hat sich Herr Sedgewick was ausgedacht. Und selbst mithilfe seines Buchs verstehe ich nicht die ganze Magic dahinter *g*

Ich hasse die Teile auch abgrundtief, aber irgendwie muss ich das ja hin bekommen.

Ich habe mir jetzt einfach einen C-Code geschnappt und mir den mal angeschaut. Danach scheint es ansich gar nicht sooo schlimm zu sein, aber trotzdem suckt das Teil einfach.

PH4Real
2007-05-20, 10:46:09
Der Tree aus der Java API ist auch als R/B-Tree implementiert. Von dem kann man sich auch die Implementierung angucken, die auch an vielen Stellen sinnvoll kommentiert ist.

EDIT: Zu deinem Problem... die Vorgehensweise ist nicht direkt festgelegt, wie man bei einem Einfügen reagieren muss. Hauptsache ist, man stellt die R/B-Eigenschaften nach jedem Einfügen her. Wie das gelingt, liegt also an einem selbst. Die Regeln dazu kann man sich selbst definieren.

Grundsätzlich sind aber immer folgende sechs Fälle nach dem Einfügen (vom Knoten k) zu unterscheiden:


parent(k) ist linkes Kind von parent(parent(k)).
1. Der „Onkel“ von k ist rot.
2. Der „Onkel“ von k ist schwarz und k ist rechtes Kind.
3. Der „Onkel“ von k ist schwarz und k ist linkes Kind.
parent(k) ist rechtes Kind von parent(parent(k)).
3 analoge Fälle

Bei dem Beispiel mit dem Applet kann man sowohl nur umfärben, als auch Links-Rotieren + Umfärben. Beides ist erlaubt.

Wenn man sich für diese Fälle jeweils einen Algorithmus überlegt (oder aus bekannten Büchern oder VL abguckt ;) ) hat man es geschafft. Das Löschen ist nochmal ein bißchen schwieriger aber ähnlich. Ach ja... für eventuelle Prüfungen würde ich mir lieber die (Iterations-) Beweise zu den Sätzen des R/B-Baumes angucken wie "Die Höhe eines Red/Black-Baumes mit n internen Knoten beträgt maximal 2 ld (n+1)" ;).

HellHorse
2007-05-20, 14:00:43
Wenn man sich vor Augen hält, dass 16 Jahre verginen zwischen der ersten und der ersten korrekten Implementation von binary search, ....

Senior Sanchez
2007-05-20, 14:17:51
Wenn man sich vor Augen hält, dass 16 Jahre verginen zwischen der ersten und der ersten korrekten Implementation von binary search, ....

...dann dürfte es RB-Trees heute noch nicht geben :D

Woher weißte das mit binary search?

Coda
2007-05-20, 15:36:01
Wenn man sich vor Augen hält, dass 16 Jahre verginen zwischen der ersten und der ersten korrekten Implementation von binary search, ....
Wie meinst du das? Was ist an binary search so unglaublich komplex?

Meinst du das hier: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Das Problem daran ist wohl, dass so große Arrays seltenst vorkommen.

HellHorse
2007-05-20, 15:41:21
...dann dürfte es RB-Trees heute noch nicht geben :D
Es geht nicht darum, ob es "geht" sondern ob es in allen möglichen Spezialfällen geht (keine Bugs hat).

Woher weißte das mit binary search?
Programming Perls (http://www.amazon.com/Programming-Pearls-2nd-Jon-Bentley/dp/0201657880) verweist auf Knuth:
Erste Publikation: 1946
Erste Publikation ohne Bugs: 1962

Senior Sanchez
2007-05-20, 16:07:29
Wie meinst du das? Was ist an binary search so unglaublich komplex?

Meinst du das hier: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Das Problem daran ist wohl, dass so große Arrays seltenst vorkommen.

Das ist ja lustig - darüber habe ich mir noch nie Gedanken gemacht, aber können in Java überhaupt so große Arrays erzeugt werden, dass diese 2^31 - 1 Elemente enthalten?

HellHorse
2007-05-20, 17:21:41
Das ist ja lustig - darüber habe ich mir noch nie Gedanken gemacht, aber können in Java überhaupt so große Arrays erzeugt werden, dass diese 2^31 - 1 Elemente enthalten?
Ja, das ist die äusserste Grenze, geht wohl am besten mit einer 64bit VM. Einen Überlauf kannst du jedoch - wie im Artikel dargelegt - schon früher bekommen.

Senior Sanchez
2007-05-20, 20:21:59
Ja, das ist die äusserste Grenze, geht wohl am besten mit einer 64bit VM. Einen Überlauf kannst du jedoch - wie im Artikel dargelegt - schon früher bekommen.

Ja, okay, aber dazu brauche ich auch riesige Arrays - oder habe ich etwas überlesen?

Coda
2007-05-20, 20:43:53
Nein stimmt schon, deshalb würde ich es auch nicht unbedingt "Bug" nennen. Zumindest ist es keiner für eine normale Anwendung.

Senior Sanchez
2007-05-20, 21:06:19
Jo, stimmt schon.
Aber diese Gedanken habe ich mir noch nie gemacht, aber das kann ja mal ganz nützlich sein zu wissen ;) So weiß ich jetzt, das mein Mergesort auch "falsch" ist ;)

Aber wenn es solche Bugs gibt, will ich gar nicht wissen, was erst bei RB noch falsch gehen kann ;)

HellHorse
2007-05-20, 21:28:52
Nein stimmt schon, deshalb würde ich es auch nicht unbedingt "Bug" nennen. Zumindest ist es keiner für eine normale Anwendung.
Ist bei einigen Leuten in produktiven Anwendungen passiert. Was willst du denen sagen? Das ihre Anwendungen nicht normal sind? Das sie das halt besser selber implementieren sollen, da das eingebaute binary search halt eben nicht für Arrays beliebiger Grössen funktioniert? Das Java gratis ist und sie besser die Fresse halten sollen?