Wozu Rot-Schwarz-Bäume?!

[Nasenbaer]

Hi,
ich würde gerne mal wissen wo man in der Praxis wirklich eine derartige Implementation bniärerer Suchbäume nutzt. Sicher besitzen sie tolle Werte bzgl. Laufzeit aber ich finde das arbeiten und vorallem ändern von Rot-Schwarz-Bäume doch ziemlich scherw zu implementieren und kann mir irgendwie nicht vorstellen, dass sowas oft genutzt wird.
Für mich als Erstsemestler war jedenfalls nicht so trivial wie mancher Professor glaubt. ;)

[Coda]

ich würde gerne mal wissen wo man in der Praxis wirklich eine derartige Implementation bniärerer Suchbäume nutzt. Viele Sprachen bieten sowas in ihrer Library, z.B. in C++ std::map (die Spezifikation erfordert zwar keine Implementierung per Red-Black-Tree, aber es ist naheliegend durch die vorgegebenen Performancecharrakteristiken).

Das ganze ist wirklich nicht so ganz trivial, da brauchst du dir keine Vorwürfe machen.

[Nasenbaer]

Achja stimmt ja STL und co bringen sowas ja eigentlich eh schon mit - nur lernt man dabei ja nicht wirklich was. :)
Ja die Aufgabe war echt heftig. Selbst unser Übungsleiter musste sich erstmal übers Wochenende Gedanken darüber machen. *fg*

[Demirug]

Das gehört in die gleiche Gruppe wie Quicksort. Den schreibt man auch nur einmal selbst und nimmt dann immer eine fertige Library

@Coda: Bist du sicher das std::map einen Baum und keine Hashmap benutzt?

[HellHorse]

Bäume machen unter anderem dort Sinn, wo nicht alle Daten im Speicher liegen, Datenbanken und so. Auch bei Indices und solchen Geschichten. So lassen sich z.B. Textindeces recht billig mittels TSTrees bauen.

Und Bäume (wie all die anderen ADTs) willst du normalerweise nicht selbst implementieren, vor allem die komplizierteren wie RB.

[Coda]

@Coda: Bist du sicher das std::map einen Baum und keine Hashmap benutzt?Ja. Hashmaps fehlen in der STL bisher komplett.

[AlSvartr]

Rot-schwarz-Baeume sind aber immerhin noch leichter zu implementieren als (2,4)-Baeume, obwohl sie im Endeffekt ja nicht wirklich unterschiedlich sind...

Aber von wegen gleiche Kategorie wie Quicksort: Vom Nervigkeitsgrad der Implementierung sind die Rot-schwarz-Baeume da doch ne ganze Ecke hoeher angesiedelt, wuerd ich behaupten ;)

[RLZ]

Ja. Hashmaps fehlen in der STL bisher komplett.
http://www.sgi.com/tech/stl/hash_map.html
:confused:

[ScottManDeath]

http://www.sgi.com/tech/stl/hash_map.html
:confused:

Sie mögen in SGIs STL implementation enthalten sein. Das heißt aber nicht, dass sie im C++ Standard mit drinne sind. Im kommenden C++ Standard sollen sie aber enthalten sein, wenn auch unter anderem Namen.

[Demirug]

Rot-schwarz-Baeume sind aber immerhin noch leichter zu implementieren als (2,4)-Baeume, obwohl sie im Endeffekt ja nicht wirklich unterschiedlich sind...

Aber von wegen gleiche Kategorie wie Quicksort: Vom Nervigkeitsgrad der Implementierung sind die Rot-schwarz-Baeume da doch ne ganze Ecke hoeher angesiedelt, wuerd ich behaupten ;)

Ich bezog mich nicht auf die Komplexität sondern das man solche Sachen meist nur einmal selbst macht.

[micki]

gibt es da eigentlich nen vorteil gegenüber avl-trees? ich fand die bisher immer angenehmer und von der performance her auch nicht nachstehend, aber alle stl immplementierungen nutzen rb-trees. y?

[Der_Donnervogel]

Viele Sprachen bieten sowas in ihrer Library, z.B. in C++ std::map (die Spezifikation erfordert zwar keine Implementierung per Red-Black-Tree, aber es ist naheliegend durch die vorgegebenen Performancecharrakteristiken).

Sun verwendet bei der TreeMap für Java auch einen Red-Black tree.

http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeMap.html

[AlSvartr]

Ich nehme an, das liegt daran, dass beim AVL-Tree im worst Case einfach mehr Rotationen notwendig werden, bei einem Rot-Schwarz-Baum aber nur eine gewisse Anzahl Rotationen (2 oder 3?) notwendig sein kann und danach Umfaerben genuegt. Achtung: Diese Aussage ist mit Vorsicht zu genießen, ich weiss es selber nicht so genau ;)

@Demirug: Wollte dir nichts unterstellen, wollts nur anmerken :)

[HajottV]

So lassen sich z.B. Textindeces recht billig mittels TSTrees bauen.

Oh, auch in der Branche (IR) tätig? :wink:

Gruß

Jörg

[ShadowXX]

Sie mögen in SGIs STL implementation enthalten sein. Das heißt aber nicht, dass sie im C++ Standard mit drinne sind. Im kommenden C++ Standard sollen sie aber enthalten sein, wenn auch unter anderem Namen.

Selbst in der MS-Implementation (also Visual Studio bzw. VC) hat hashmaps drinne....und das schon länger.

[Nasenbaer]

Ich nehme an, das liegt daran, dass beim AVL-Tree im worst Case einfach mehr Rotationen notwendig werden, bei einem Rot-Schwarz-Baum aber nur eine gewisse Anzahl Rotationen (2 oder 3?) notwendig sein kann und danach Umfaerben genuegt. Achtung: Diese Aussage ist mit Vorsicht zu genießen, ich weiss es selber nicht so genau ;)

Ja, wenn ich die Vorlesung noch richtig in Erinnerung, dann sind es nie mehr als 3 Rotationen aber AVL-Bäume haben den Vorteil einer höheren Ausgeglichenheit als RB-Trees.

Aber naja das geht ja auch noch alles, ich frag mich nur wer freiwillig Theoretische Informatik als Vertiefungsrichtung wählt - das is ja nun echt krank. :ulol:

[Trap]

Ach, in der theoretischen Informatik gibt es noch ganz andere Sachen als Datenstrukturen. Zum Beispiel den Fixpunktsatz von Kleene ;)

[zeckensack]

Hi,
ich würde gerne mal wissen wo man in der Praxis wirklich eine derartige Implementation bniärerer Suchbäume nutzt. Sicher besitzen sie tolle Werte bzgl. Laufzeit aber ich finde das arbeiten und vorallem ändern von Rot-Schwarz-Bäume doch ziemlich scherw zu implementieren und kann mir irgendwie nicht vorstellen, dass sowas oft genutzt wird.
Für mich als Erstsemestler war jedenfalls nicht so trivial wie mancher Professor glaubt. ;)Rot-Schwarz-Bäume haben den Vorteil dass die Balance des Baums immer mindestens so gut ist wie bei einfachen Bäumen, im Mittel besser, und in (für normale Bäume) pathologischen Fällen viel besser.

Das lohnt sich durchaus für Bäume die dynamisch veränderbar sein sollen. Statische Bäume kann man auch statisch ausbalancieren, und dann bringt der zusätzliche Aufwand natürlich nichts.

Die Implementation ist etwas haarig, aber das macht man auch nur einmal. Praktisch kannst du dir das auch gleich ganz schenken und dich auf die STL-Implementierung des Compilers verlassen.

ZB implementieren sowohl MS-Compiler als auch GCC std::map gleich als red-black-tree. Beide setzen auf Code auf der 1994 von HP geschrieben wurde =)

Siehe zB %gccroot%/include/c++/map, %gccroot%/include/c++/bits/stl_tree, %msvcroot%/include/map (Copyright-Vermerk am Ende) und %msvcroot%/include/xtree.

[Nasenbaer]

Ach, in der theoretischen Informatik gibt es noch ganz andere Sachen als Datenstrukturen. Zum Beispiel den Fixpunktsatz von Kleene ;)
Naja bei uns gehört die ja nicht zur theoretischen Informatik - deshalb ist es vielleicht ja auch noch erträglich. *fg*
Aber sowas wie Turing-Maschine, primitiv-rekursive Funktionen ist doch wohl mehr als weit von der Prxis entfernt!? Für mich ist sowas halt ziemlicher Nonsens.

[Trap]

Die Turing-Maschinen selbst sind praxisfern, die Sätze darüber nicht, die gelten für alle Programmiersprachen. Dafür dass man etwas über alle Programmiersprachen sagen kann muss man halt ein bisschen mehr Aufwand treiben...

[Coda]

Selbst in der MS-Implementation (also Visual Studio bzw. VC) hat hashmaps drinne....und das schon länger.Sie wurde ab .NET 2003 aber in den stdext-Namespace verschoben weil sie in std eben nicht hingehört. ISO-C++ sieht keine Hashmaps vor.

Ach, in der theoretischen Informatik gibt es noch ganz andere Sachen als Datenstrukturen. Zum Beispiel den Fixpunktsatz von Kleene ;)Wollte grad sagen. Oder das tolle Pumping-Lemma X-D

[Nasenbaer]

Die Turing-Maschinen selbst sind praxisfern, die Sätze darüber nicht, die gelten für alle Programmiersprachen. Dafür dass man etwas über alle Programmiersprachen sagen kann muss man halt ein bisschen mehr Aufwand treiben...
Sicher denkt man sowas nicht aus, weil man gerade nichts zu tun hat aber man muss ja auch nicht alles wissen. :D
Mir reicht schon, dass mein Rechnersysteme Dozent nicht ordentlich erklären konnte wie eine dezimale rationale Zahl als Gleitkomma-Zahl nach IEEE Standard dargestellt wird. Dat konnte wikipedia weit besser. Aber Hauptsache unzählige Titel vorm Namen haben - das is wichtig...

[Senior Sanchez]

Sicher denkt man sowas nicht aus, weil man gerade nichts zu tun hat aber man muss ja auch nicht alles wissen. :D
Mir reicht schon, dass mein Rechnersysteme Dozent nicht ordentlich erklären konnte wie eine dezimale rationale Zahl als Gleitkomma-Zahl nach IEEE Standard dargestellt wird. Dat konnte wikipedia weit besser. Aber Hauptsache unzählige Titel vorm Namen haben - das is wichtig...

Naja, aber alles wissen kannste nicht.

Ich pauke gerade ziemlich viel mitm Sedgewick und was da an Details usw. vermittelt wird, das kannst du dir einfach nicht merken.

Wennde nun wissen willst wie Gleitkomma-Zahlen oder solche kleinen Geschichten genau dargestellt werden, dass schauste nach und vergisste danach wieder weil du es nie wieder im Detail brauchst.

Aber ne Frage zu den Rot-Schwarz-Bäumen *g*

Ich habe da ja momentan auch meine liebe Freude damit, besonders mit der Rotation bzw. Doppelrotation (afaik brauch man damit maximal 2 Rotationen). Ich bekomms einfach nicht wirklich rein in den Schädel. Mir hilft es ja son bissl mir das wieder als Top-Down-2,3,4-Baum vorzustellen, aber es ist echt haarig.

Kennt da jemand ne gute Anleitung die einem das zum Beispiel grafisch zeigt, wie die Rotation abläuft?

[Baalzamon]

Kennt da jemand ne gute Anleitung die einem das zum Beispiel grafisch zeigt, wie die Rotation abläuft?

Vielleciht hilft dir dieses Applet (http://gauss.ececs.uc.edu/RedBlack/redblack.html) weiter.

Die Schritte sind einzeln "durchklickbar" und es gibt ein Textfenster mit einer kleinen Erklärung, warum jetzt was gemacht wurde.

[Nasenbaer]

Naja, aber alles wissen kannste nicht.
Aber ne Frage zu den Rot-Schwarz-Bäumen *g*

Die Folien zur Vorlesung vom 4.1.2006 würd ich dir da empfehlen. Und ansonsten noch ganz unten auf der Seite - dort sind Links zu Animationen.

http://www.informatik.uni-rostock.de/mmis/courses/ws0506/23001/

[Senior Sanchez]

Danke Baalzamon und Nasenbaer :)

Ich glaube, jetzt habe ich es halbwegs verstanden.
Es wird rotiert, sobald die zwei rote Verbindungen hintereinander sind und abhängig von der Orientierung wird entweder ne einfache Rotation oder eine Doppelrotation durchgeführt.

Ansich ganz logisch, wenn man sich das anschaut, aber erstmal darauf kommen ;)

[Nasenbaer]

Danke Baalzamon und Nasenbaer :)

Ich glaube, jetzt habe ich es halbwegs verstanden.
Es wird rotiert, sobald die zwei rote Verbindungen hintereinander sind und abhängig von der Orientierung wird entweder ne einfache Rotation oder eine Doppelrotation durchgeführt.

Ansich ganz logisch, wenn man sich das anschaut, aber erstmal darauf kommen ;)
Das Problem ist anzugeben wie beim Einfügen/Löschen rotiert werden soll. Es gibt da etliche Fälle die betrachtet werden müssen. Und das macht ne fixe Implementation gerade so schwer und fehleranfällig.

[CannedCaptain]

Bin ich froh, dass ich das nicht mehr machen muss. Mir als Physiker reicht es die Laufzeit zu kennen und dementsprechend nutze ich dann die Datenstruktur. Ist es nicht immer so, dass man im Endeffekt den Scheiß einmal nervenaufreibend programmiert und dann stur anwendet. Wobei ich mich manchmal ernsthaft fragen muss wie nerd man sein muss, Datenstrukturen dieser Komplexität zu entwerfen, mich erfüllt das immer mit tiefsten Respekt.
Das schlimmste an der Sache ist, dass einem Informatiker noch weniger Ruhm zukommt als einem Mathematiker oder Physiker, wenn er solche hochkomplexen Gebilde versteht und selbst kreiert. Es gab in den Naturwissenschaften schon für einfachere Sachen Nobelpreise.

[Senior Sanchez]

Das Problem ist anzugeben wie beim Einfügen/Löschen rotiert werden soll. Es gibt da etliche Fälle die betrachtet werden müssen. Und das macht ne fixe Implementation gerade so schwer und fehleranfällig.

Na im Grunde sinds doch 8 Fälle, oder? (4 Grundfälle, aber aufgrund der Symmetrie von links und rechts verdoppelt es sich)

@CannedCaptain

Ich werde auch froh sein, wenn ich das nicht in der Praxis anwenden muss sondern ne vorgefertigte Datenstruktur nutzen kann *g*
Sedgewick, dessen Buch ich gerade lese, hat ja den RBTree miterfunden und er erklärt das echt so, als sei es spielend einfach *g*

Aber gut, mir reicht das gröbste zu wissen.

Für Informatiker gibts doch btw den Alan Turing - Award. Rivest, Shamir und Adleman haben den doch mal für die Entwicklung des RSA-Kryptosystems bekommen.

[Nasenbaer]

Na im Grunde sinds doch 8 Fälle, oder? (4 Grundfälle, aber aufgrund der Symmetrie von links und rechts verdoppelt es sich)
Reicht dir das denn noch nicht? Ich fands übel und selbst die Übungsleiter hatte absolut keinen Durchblick bei der Sache. :)

[Senior Sanchez]

Reicht dir das denn noch nicht? Ich fands übel und selbst die Übungsleiter hatte absolut keinen Durchblick bei der Sache. :)

Und ob mir das reicht! *g*

Ich finds echt übel, aber immerhin weiß ich jetzt ungefähr, wann rotiert werden muss *gg* dazu nutze ich dann in irgendwelchen klausuren oder texten am besten immer die nicht näher spezifizierte Funktion rotate() :D

[AlSvartr]

Also ich finde Goodrich/Tamassia haben das in ihrem Buch bzw. den dazugehörigen Folien recht gut und auch anschaulich erklärt. Wenn jemand rausfinden möchte, ob ich damit richtig liege..PM genügt ;)