Diskussion:Rot-Schwarz-Baum

Zum Archiv

Wie wird ein Archiv angelegt?

Auf dieser Seite werden Abschnitte halbmonatlich automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

Abgeschlossenes Review vom 13. Okt 2005

Nachdem ich den deutschen Artikel in den letzten Tagen mit Hilfe der Informationen auf der englischen Wikipedia ordentlich ausgebaut habe bin ich nun mit meinem Wissen was man an dem Artikel noch verbessern könnte am Ende, weswegen ich euch mal fragen wollte was euch an dem Artikel noch fehlt. Ich würde gerne noch eine Sektion über die Verwendung von Rot-Schwarz Bäumen einbauen, aber habe nichts gefunden wo sie wirklich verwendet werden... Ansonsten habe ich versucht trotz der recht komplexen Materie die gute alte Oma nicht gleich am Anfang zu verschrecken. Also zu gut deutsch: Was kann man an dem Artikel noch verbessern damit er es vielleicht mal in die lesenswerten schafft? Regnaron 13:50, 13. Okt 2005 (CEST)

Hallo Regnaron! Klasse Arbeit! Ein paar Kleinigkeiten: Generell sollte in der WP zur Darstellung von Algorithmen lieber Pseudocode verwendet werden, weil das (für Laien) leichter lesbar ist. Allerdings wäre hier eine Änderung vielleicht etwas aufwändig. Vielleicht kannst du wenigstens den Code und die Kommentare etwas eindeutschen. Zweitens: warum heißen die Blattknoten alle "NIL"? ;-) Drittens: Die Gliederung könnte man etwas verschönern. Beim Höhenbeweis benutzt du immer Fettdruck als Abschnittsüberschriften, warum nimmst du nicht normale Unterüberschriften? --Kurt seebauer 14:49, 13. Okt 2005 (CEST)

Hi! Danke erstmal fürs Feedback! Zum Code: Den habe ich 1 zu 1 aus der Englischen Wikipedia übernommen, und da war es halt C-Code. Aber ok, die Kommentare kann ich gerne noch eindeutschen. Die Blattknoten heißen alle NIL, weil sie in der Literatur meistens so genannt werden. (müsste irgendwo ganz oben stehen dass diese Knoten keine Daten tragen und eigentlich nur "terminalknoten" sind. (aber mal schauen ob ich das noch ein bisschen deutlicher zur Geltung bringen kann) Zur Gliederung: Anfangs hatte ich beim Höhenbeweis Unterüberschriften statt der Fettschrift, fand das aber nicht so toll weil dadurch das Kapitel Höhenbewis in der Übersicht extrem groß erschien. (Hatte dann halt auch nochmal drei Unterabschnitte, wie der Teil über die Operationen an sich) Aber wenn die anderen meinen dass eine Gliederung hier besser wäre werde ich sicherlich nicht an der Fettschrift festhalten. (wollte halt nur erreichen dass es nicht so aussieht als ob der Höhenbeweis einen großteil des Artikels ausmacht) Regnaron 15:02, 13. Okt 2005 (CEST)

So, habe zwar nochmal wegen Pseudocode nachgesehen, aber IMHO wird es dadurch dass man left_child(n) statt n->left schreibt nicht wirklich sehr viel leichter. Der Code verwendet ja keine großen C Syntax Sonderheiten. (die eine die er verwendet hat (x ? a : b) habe ich durch ein normales if-then-else ersetzt) Aber nachdem der Artikel ja nun keine großen Kanten mehr zu haben scheint (jedenfalls beschwert sich keiner *g*) wollte ich noch ein letztes Mal um Feedback bitten bevor ich den Artikel mal bei den Lesenswerten vorschlage. Und da ich ihn da halt ungern verheizen würde: Falls irgendwas nicht stimmt oder nicht stimmig ist: Bitte sagen. Regnaron 20:52, 24. Okt 2005 (CEST)

Falls möglich, sollte man noch einen Link auf eine Implementierung angegeben. Ich würde hier die Programmiersprache Pascal bevorzugen. (viele Lehrbücher verwenden ja ebenfalls Pascal Syntax) Die Vor- und Nachteile des Rot-Schwarz-Baumes fehlen vielleicht noch. Man könnte im Artikel Suchbaum die verschiedenen Suchbäume auflisten und deren Leistungsfähigkeit bewerten und Anwendungsgebiete zeigen. --Shmia 11:11, 28. Okt 2005 (CEST)

Ich denke, als "lesenswerter" geht er locker durch. Ich würde ihn jetzt dort einstellen. Vielleicht kommt bei der Diskussion dort auch noch ein wenig mehr Feedback. --Kurt seebauer 20:18, 31. Okt 2005 (CET)

Jup, wollte ihn eh demnächst da einstellen. Habe die letzten Tage nochmal versucht die Wünsche von Shmia zu erfüllen, und nochmal nach Einsatzgebieten von Rot-Schwarz-Bäumen gegooglet, aber leider habe ich da nichts wirklich verwertbares gefunden. Werde also hiermit das Review offiziell abschließen und ihn mal Kandidieren lassen ;-) Regnaron 22:01, 31. Okt 2005 (CET)

XEN benutzt RB-Trees um diverse Checks schneller zu machen. Habs mal gesehen und würde es mir näher anschauen, falls Bedarf besteht, einen Anwendungsfall näher einzuarbeiten. lg --Chris2002 17:45, 22. Jan. 2011 (CET)

Abgeschlossene Lesenswert-Diskussion vom 31. Okt 2005

Ein Rot-Schwarz-Baum ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, welche sehr schnellen Zugriff auf die in ihr gespeicherten Werte garantiert. Rot-Schwarz Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben, welcher sie symmetric binary B-trees nannte.

•  Neutral Da ich der Hauptautor bin enthalte ich mich der Stimme, aber ich denke nachdem der Artikel nun einige Wochen im Review war sollten inzwischen die meisten Ecken und Kanten abgeschliffen worden sein, sodass der Artikel durchaus Lesenswert ist. Weitere Anregungen sind natürlich ebenfalls immer Willkommen. Regnaron 23:01, 31. Okt 2005 (CET)

• von mir gibts natürlich ein fettes pro! --Kurt seebauer 13:39, 1. Nov 2005 (CET)
• pro - gefällt mir und ist auch für den Laien verständlich -- Achim Raschka 08:35, 2. Nov 2005 (CET)
•  Pro fein gemacht. --Kinley 09:55, 3. Nov 2005 (CET)

Für Laien verständlich? Ich bin erst seit 20 Jahren Anwendungsentwickler - wie lange brauche ich noch, um Laie zu werden? :) --93.198.79.80 09:10, 22. Aug. 2017 (CEST)

@93.198.79.80: Lieber Anwendungsentwickler! Da wäre es natürlich extrem hilfreich, wenn Du eine Andeutung machen würdest, was für Dich unverständlich ist. --Nomen4Omen (Diskussion) 14:15, 22. Aug. 2017 (CEST)

Verbesserungsvorschlag für die Grafiken

Sehr schöne Seite. Ich habe nur noch einen kleinen Verbesserungsvorschlag für die Grafiken: Die grauen Knoten sollten mehr in Richtung Schwarz geändert werden und/oder die roten Knoten müssten heller sein, denn bei den aktuellen Grafiken erscheinen in der Graustufendarstellung (z.B. beim Drucken) verwirrenderweise die roten Knoten dunkler als die Schwarzen. --Clemo 18:30, 8. Dez 2005 (CET)

Hi! Habe mir mal erlaubt eine neue Überschrift für deinen Beitrag anzulegen, da er eigentlich ja nicht unter die Lesenswert Diskussion fällt. So, nun aber zum eigentlichen Thema: Danke erst einmal für dein Feedback, aber leider kann ich selbst an den Bildern nicht viel ändern. Ich habe sie nur aus der englischen Wikipedia in die Commons verschoben und von dort aus eingebunden. Bin also leider nicht der Autor der Bilder, und habe somit auch keine Orginale von den Bildern, sodass ich mal schnell die Farbe ändern kann... Und dafür, selbst die Bäume neuzumalen, sodass sie schön aussehen, dafür gehen meine Kentnisse mit graphviz leider noch nicht weit genug :-( Aber ich kann gerne mal den Autor fragen ob der die Orginaldateien hat, damit ich da die Farbe dann ein bisschen anpassen könnte. Regnaron 19:16, 8. Dez 2005 (CET)

O-Notation

Meine Anmerkung zu dem Artikel ist, daß in der O-Notation unerheblich ist, welcher Logarithmus angegeben ist, da die angegebene Funktion ja mit einem beliebigen konstanten Faktor multipliziert werden kann. Üblicherweise wird deshalb nur O(log n) geschrieben.

Stimmt, es ist in der Tat unerheblich welchen Logarithmus man verwendet, aber da es sich erstens um einen Binärbaum handelt, und zweitens in der Informatik eh meistens ein zweierlogarithmus genommen wird, denke ich nicht, dass die nennung der Basis hier stört. Regnaron 14:33, 4. Mär 2006 (CET)

Ich habe mich gerade das Selbe gefragt und würde die Basis entfernen. Sie anzugeben ist unüblich und irritiert schon, gerade weil man sich fragt warum sie denn hier angegeben ist. -- octo 08:09, 18. Jun. 2009 (CEST)

Wurde das bereits geändert? Ich habe den Artikel gerade gelesen und kann das nicht finden. --Martin Thoma 17:17, 10. Jun. 2012 (CEST)

Fehler: Eigenschaften des Rot-Schwarz-Baums

Hallo. Ich meine zu wissen, dass die Eigenschaft Nr. 2 im Artikel "Die Wurzel des Baums ist schwarz." so nicht stimmt. Ein Baum ist auch ein Rot-Schwarz-Baum wenn die Wurzel rot ist (solange die anderen Eigenschaften eingehalten werden). Die Wurzel immer schwarz zu halten vereinfacht nur die Arbeit mit dem Baum weil der Fall der roten Wurzel nicht mehr auftreten kann. Kann das jemand bestätigen? --Yarin Kaul 04:22, 23. Apr 2006 (CEST)

Hi! Ich habe die Eigenschaften des Rot-Schwarz Baumes aus dem in der Literatur angegebenen Buch Introduction to Algorithms und der englischen Wikipedia Artikel übernommen, und dort ist ein Rot-Schwarz-Baum unter anderem durch eine schwarze Wurzel definiert. Und auch wenn mir momentan zugegebenermaßen kein Fall einfällt, wo man die Eigenschaft der schwarzen Wurzel wirklich braucht, so gehe ich mal davon aus, dass sie irgendeinen Sinn hat :-) Regnaron 07:51, 23. Apr 2006 (CEST)

Hallo nochmal! Hier steht:

In der Implementierung des Einfuegen Algorithmus haben wir eine Vereinfachung vorgenommen. Wir halten die Wurzel unseres Baumes immer schwarz. Dies hat zur Folge, dass der Fall 2 niemals vorkommt, da die Wurzel nie rot ist[Cormen]. Die Wurzel stets schwarz zu halten ist legitim, weil damit zwar der Rang des Baumes um 1 erhoeht wird, aber keine Eigenschaft von Rot-Schwarz Baeumen verletzt wird.

Demnach wäre eine immer schwarze Wurzel tatsächlich eine Vereinfachung des Rot-Schwarz-Baums. Ich werde mal schauen, ob es dafür noch andere Quelle zur Bestätigung gibt. -- Yarin Kaul 13:01, 25. Apr 2006 (CEST)

Und nochmals Hi!

Hm, deine Quelle widerspricht sich irgendwo ein bisschen habe ich das Gefühl. Der Satz liest sich für mich wie folgt: Wir halten die Wurzel immer schwarz, weil das einfacher ist, und weil die Wurzel nach Cormen eh nie rot (also immer schwarz) ist. (dann braucht man sie aber nicht extra schwarz zu halten...) Aber im Grunde bestätigt sie ja nochmal meine Aussage, dass RB-Bäume eben (zumindest im Cormen) unter anderem durch eine schwarze Wurzel definiert sind, da sie selbst dessen Definition übernimmt. Aber wie gesagt: Diese Definition über die Schwarze Wurzel ist eigentlich auch die mir geläufige. Regnaron 13:15, 25. Apr 2006 (CEST)

Fehlt dem Baum nicht noch eine weitere Eigenschaft: Die Höhe ist überall gleich, wobei die roten Elemente nicht mitgezählt werden. Schliesslich ist ein Rot-Schwarz-Baum nur eine Impementationsform eines 2-3-4-Baums (Ein schwarzes Element mit seinen direkten unteren roten Elementen bildet einen einzigen Knoten eines 2-3-4-Baums). Dies erklärt auch die Frage, ob die Wurzel schwart sein muss. --84.73.107.48 18:54, 1. Apr. 2010 (CEST)

Was du ansprichst ist die sog. Schwarz-Höhe und die steht im Artikel (Eigenschaft 5. Diese Eigenschaft ist sogar noch etwas stärker.) --Martin Thoma 17:21, 10. Jun. 2012 (CEST)

C-Code

Beim Einfuegen im Fall 1 wird folgender Code angegeben: void insert_case1(node n) {

   if (n->parent == NULL)
       n->color = BLACK;
   else
       insert_case2(n);

}

eigentlich ist der else-Zweig doch vollkommen ueberfluessig?

Wieso? Wenn du in einen nichtleeren Baum etwas einfügen willst, dann hat der Eingefügte Knoten einen Vater. Dieser Vater kann wie das Kind rot sein, und somit solltest du den Fehler beheben. Und genau dies geschieht durch das "weiterdelegieren". Oder verstehe ich dich gerade vollkommen falsch? Regnaron 13:12, 19. Jun 2006 (CEST)

Frage zu Anzahl der Rotationen (Kann mir keiner weiterhelfen ????)

Hi, hab da mal ne Frage. Angenommen ich habe einen balancierten Red-Black Tree der nur aus schwarzen Knoten besteht. Der muesste ja OK sein. Wenn ich jetzt einen der unteren Knoten lösche, wieviele Rotationen benötige ich, um die RB-Eigenschaft (gleichen Anzahl schwarzer Knoten für jeden Pfad) wiederherzustellen ? Reicht da wirklich eine konstante Anzahl von Rotationen ? Wolfgang-gerlach 18:55, 16. Nov. 2006 (CET)

--

Dieser Fall wird nie auftreten, da wenn du den Baum aufbaust immer rote Knoten eingefügt werden!

Grafische Darstellungen des Baumes sind fehlerhaft

Da im C-Code vom Kind auf den Vater geschlossen werden kann, ist die Darstellung der Bilder falsch. Hier müssten dann jeweils noch Zeiger von den Kindern zurück auf die Eltern führen. --77.179.216.106 12:02, 04. März 2007 (CEST)

Fehlerhafte Beschreibung des Löschvorgangs

Wenn man die Wurzel löscht, bedeutet dies keineswegs, dass das Schwarztiefenkriterium erhalten bleibt wie folgendes Beispiel verdeutlicht: Man erstelle z.B. mit dem im Artikel verlinkten Java Applet folgenden Baum: 472,154,892,48,356,707,978,363,923,992

Nun Lösche man die Wurzel 472 nach dem Prinzip des kleinsten Elements im rechten Teilbaum. 472 wird also durch den schwarzen Knoten 707 ersetzt, wodurch das Schwarztiefenkriterium verletzt wird. --77.178.227.187 12:23, 20. März 2007 (CEST)

Meiner Ansicht nach nicht wirklich. Schwarze Kanten sind nur diejenigen oberhalb von schwarzen Knoten. Nach dem Löschen der Wurzel sind also folgende Kanten schwarz: 154->48, 154->356, 892->707, 892->978 . Schwarztiefe überall 1, alles wunderbar. (Annahme: Ohne Blätter). --Benutzer:85.127.149.99 10:18, 10. März 2008 (CET)

Wenn der Knoten zwei Kinder hat und es handelt sich bei dem Knoten um die Wurzel, kommt es wirklich zu Problemen. (Bsp: 38, 19, 41, 12, 31, 8 -> 38 löschen -> Rot-Schwarz-Tiefenregel verletzt). Ausserdem wird der Fall das es keine Kinder gibt nicht behandelt. (Bsp: 38, 31, 41 -> 41 löschen -> wieder Rot-Schwarz-Tiefenregel verletzt)

Artikel beschreibt nur bottom-up-Variante

Es sollte zumindest erwähnt werden, dass hier die bottom-up-Variante beim Einfügen etc. verwendet wird, in vielen Lehrbüchern wird der top-down-Algorithmus beschrieben - mich hat es sehr verwirrt da die hier vorgestellte Variante als DIE Variante rüberkommt, so als gäbe es die andere (laut meinem Buch sogar häufigere) Vorgehensweise gar nicht.

-- 82.150.196.185 17:56, 13. Jun. 2007 (CEST)

C-Code für Einfügen im Fall 3

Hallo,

in Fall 3 der Einfügeoperation ist als Voraussetzung angegeben "Sowohl der Onkel(U) als auch der Vater(P) des neuen Knotens sind rot." Im C-Code darunter wird aber lediglich auf die Existenz eines roten Onkels(U) geprüft, d.h. wird auch ein Farbtausch bei P, G und U gemacht, wenn der Vater(P) schwarz ist.

Regel 4 "Ist ein Knoten rot, so sind beide Kinder schwarz" kann nicht umgedreht werden.

Hallo auch.

Wenn ich das richtig verstanden habe, kann in insert_case3 der Vater nicht schwarz sein, da die Funktion sonst nicht aufgerufen werden würde (siehe insert_case2). -- Haeld 11:21, 2. Aug. 2008 (CEST)

replace-Funktion

Mich würde noch interessieren, was die replace-Funktion genau macht. Ersetzt sie nur n durch das Kind oder tauscht sie beide miteinander?

Du meinst vermutlich replace_node, oder? Das sollte wohl das hier machen:

Falls der zu löschende Knoten zwei Kinder hat (keine NIL-Knoten), so sucht man entweder den größten Wert im linken Teilbaum oder den kleinsten Wert im rechten Teilbaum des zu löschenden Knotens, kopiert diesen Wert in den eigentlich zu löschenden Knoten, und entfernt den gefundenen Knoten aus dem Rot-Schwarz-Baum.

--Martin Thoma 09:49, 15. Jun. 2012 (CEST)

Löschen mit höchstens einem Kind unlogisch!?

Hallo, ist nicht automatisch die Schwarztiefe verletzt, wenn man in einem R-S-Baum einen schwarzen Knoten hat, der nur ein einziges Kind hat, das schwarz ist? Wie kann man dann also diesen Sonderfall aufgreifen bezüglich der Löschung von Elementen?

MfG! (nicht signierter Beitrag von 79.216.61.155 (Diskussion | Beiträge) 23:12, 18. Mär. 2010 (CET))

Zwei schwarze aufeinanderfolgende Knoten sind durchaus möglich. Die Situation könnte zum Beispiel beim Löschen eines roten Knotens eintreten, wenn dieser sowohl einen schwarzen Eltern- als auch einen schwarzen Kindknoten besitzt. Die Schwarztiefe würde dabei nicht verletzt werden.--Sinuhe20 09:17, 15. Okt. 2011 (CEST)

Da an der entsprechenden Stelle im Artikel, bei der von einem schwarzen Knoten mit nur einem Kind (lt. Artikel "sein Kind"), das schwarz ist, die Rede ist, aus dem Baum noch nichts gelöscht wurde, gibt es für eine solche Knotenkombination nur eine Möglichkeit: ein schwarzes Blatt, bei dem einer der NIL-Knoten als "sein Kind" ausgewählt wurde. Somit ist es etwas verwirrend, wenn man von "der Fall, wenn sowohl der zu löschende Knoten als auch sein Kind schwarz sind", redet, wo dies doch nur passieren kann, wenn ein schwarzes Blatt gelöscht werden soll.--94.135.230.162

Sprachliche Qualität: Schachtelsätze

Durch seine langen, verschachtelten Kettensätze merkt man dem Artikel seine englische Herkunft leider deutlich an. Ein Beispiel:

"Um zu verstehen, warum diese fünf Eigenschaften eine obere Schranke für die Laufzeit garantieren, reicht es sich zu verdeutlichen, dass aufgrund der vierten Eigenschaft auf keinem Pfad zwei rote Knoten aufeinander folgen dürfen, weswegen sich auf dem längsten Pfad immer ein roter Knoten mit einem schwarzen Knoten abwechselt, während auf dem kürzesten Pfad nur schwarze Knoten vorhanden sind."

Die deutsche Sprache mag im Vergleich zur englischen nicht so kompakt sein, bietet aber andere Möglichkeiten zur Darstellung komplexer Sachverhalte. Teilt jemand mit mir diese Auffassung? Ich würde mir bei Gelegenheit einmal Gedanken machen, wie sich solche monströsen Sätze verständlicher schreiben lassen. Für Ratschläge wäre ich dankbar.

-- Strathausen 13:59, 1. Jun. 2010 (CEST)

Ja, ich teile deine Beobachtung. Grüße --Uncopy 15:16, 25. Okt. 2010 (CEST)

Fehlerhafter Kommentar im Beispielcode zu Löschen?

Im Abschnitt Löschen scheint mir der Kommentar in der Beispielimplementierung /* Vorbedingung: n hat mindestens ein echtes Kind (keine zwei Nullzeiger) */ unlogisch und nicht zum Text zu passen. Sollte die Bedingung nicht sein, dass n höchstens ein echtes Kind hat? Diese Annahme wird durch den erklärenden Text und die weitgehend identische Codestelle in der englischen Wikipedia gestützt. Oder habe ich einen kleinen, aber wichtigen, Unterschied übersehen? (nicht signierter Beitrag von 134.93.136.193 (Diskussion) 19:40, 18. Apr. 2011 (CEST))

Ja richtig, bei zwei echten Kindern ist die Löschoperation nicht erlaubt.--Sinuhe20 08:47, 15. Okt. 2011 (CEST)

Übersicht zu Komplexität, Vergleich mit AVL-Baum

Im Vergleich zu AVL-Baum fehlt hier eine Übersicht zur Komplexität der Operationen. Überhaupt fällt mir auf, dass sich die beiden Artikel deutlich unterscheiden: Hier findet man Code-Schnipsel, beim AVL-Baum mehr "mathematische" Notation.

Mir persönlich gefällt der Artikel zum AVL-Baum vom Stil her besser, während dieser hier als lesenswert gekennzeichnet ist. Heißt das, dass ich mit meiner Meinung alleine bin? -- Christian Gawron 17:53, 13. Mai 2011 (CEST)

Hallo Christian, ich finde die Tabelle auch schön. Aber ich hab auch gerne Übersichtstabellen in Artikeln und musste schon mehrfach feststellen, dass ich in der Wikipedia damit eher die Außnahme bin.

Die Tabelle müsste in etwa so aussehen:

Rot-Schwarz-Baum
	Komplexität
Platz	O(n)
Operation	im Mittel	Worst case
Suchen	O(log n)	O(log n)
Traversieren	?	?
Min, Max	O(log n)	O(log n)
Einfügen	?	?
Löschen	?	?
n  Knoten im Baum †  ohne Navigation
Tabelle 1: Platz- und Zeit-Komplexitäten

Ich glaube was bei Traversierung im AVL-Artikel steht ist falsch. Ich frage dort nochmals nach.

--Martin Thoma 18:19, 10. Jun. 2012 (CEST)

Verwendung von Rot-Schwarz-Bäumen

Weiter oben taucht ja schon die Frage auf: Wo werden Rot-Schwarz-Bäume verwendet? Eine Antwort: Im Java Developer's Kit sind laut Doku die Klassen TreeSet und TreeMap als Rot-Schwarz-Bäume implementiert. Soll ich mal einen Link zur JDK-API ausgraben und als Beleg in den Artikel eintragen? -- UKoch 13:27, 1. Jun. 2011 (CEST)

Das wäre toll, wenn du das einarbeiten könntest. Man könnte vielleich einen neuen Abschnitt vor "Weitere Bäume" machen, z.B. "Verwendung von Rot-Schwarz-Bäumen". Da gibts doch sicher auch Systemnahe beispiele, oder? --Martin Thoma 09:35, 15. Jun. 2012 (CEST)

Ich hab's eingearbeitet. Was verstehst Du unter systemnahen Beispielen? -- UKoch (Diskussion) 20:49, 7. Sep. 2014 (CEST)

Eigenschaften

Im Artikel heißt es:

"während auf dem kürzesten Pfad nur schwarze Knoten vorhanden sind".

Irgendwas kapiere ich da nicht: In der Abb gibt es 2 kürzeste Pfade (13,8,11) und (13,17,15) und beide enthalten einen roten Knoten, nämlich den mittleren. -- Nomen4Omen 17:13, 29. Feb. 2012 (CET)

Gemeint ist, dass der kürzest mögliche Pfad in einem gegebenem Rot-Schwarz-Baum, der keine Eigenschaft von R-S-Bäumen verletzt, nur aus schwarzen Knoten besteht. Das muss so sein, da die Schwarz-Höhe konstant sein soll und somit nur die roten Knoten die Höhe variiren. --Martin Thoma 09:30, 15. Jun. 2012 (CEST)

Absatz 2.2 Fall 4 : zwei aufeinander folgende rote Knoten

im Fall vier unter dem Abschnitt 2.2 "Einfügen" wird der neue, rote Knoten unter einem vorhandenen, roten Knoten platziert. Das verletzt doch die 4. Eigenschaft, nachder auf einen roten, immer ein schwarzer Knoten folgen muss, oder habe ich was übersehen?--91.11.41.233 19:18, 29. Dez. 2012 (CET)

Der Fall 4 dient lediglich dazu den Baum auf Fall 5 vorzubereiten. Fall 5 dient dazu, zwei aufeinanderfolgende rote Knoten zu korrigieren. --ErikBortscht (Diskussion) 23:55, 28. Jun. 2015 (CEST)

Änderungen am 2013-11-26

1. Ich habe die (vormals zweite) Regel "Die Wurzel ist schwarz" zur didaktischen Taktik, die die Anzahl der Fallunterscheidungen geringer hält, heruntergestuft. Ich denke, das ist legitim: Mehlhorn und Sedgewick haben sie auch nicht drin.
2. Beide ziehen auch das Einfärben in 2 Farben "vor die Klammer". Will sagen: Die übrig bleibenden 3 Forderungen werden an einen 2-gefärbten Binärbaum gestellt, damit er ein RB-Baum wird.
3. Den Begriff Schwarzhöhe habe ich durch Schwarztiefe des Teilbaums ersetzt. Man könnte natürlich auch sagen: Schwarztiefe eines Baums ist von der Wurzel zum Blatt, und Schwarzhöhe ist vom Blatt zu einem Knoten. Aber so stand's ja nicht da.
4. Obere Schranke ist natürlich falsch, die gibt es nämlich nicht, allenfalls für ^Laufzeit⁄_Logarithmus.
5. Den Fall Löschen Fall 1: habe ich nicht verstanden. Beim Nachlesen im Englischen habe ich entdeckt, dass dort fürs Löschen ganz neue Namen für die relevanten Knoten vergeben wurden, und N nicht mehr den Konfliktknoten, sondern "non-leaf (non-null) child N" ist. Es wurden aber auch viele andere neue Knotennamen vergeben. Also ich lass da erstmal die Finger von, betrachte die Sache aber als ernst.
6. Es gibt ja oberhalb dieses Abschnitts noch viele Fragen etc., von denen ich nicht weiß, ob sie gelöst wurden.

--Nomen4Omen (Diskussion) 17:24, 26. Nov. 2013 (CET)

Ich muss revidieren: N, was im Englischen "non-leaf (non-null) child N" ist, heißt im Deutschen auch beim Löschen Konfliktknoten.
Frage: Ist der Fall Löschen Fall 1: einfach der, beim dem in einem Baum von 2 Knoten einer gelöscht wird? --Nomen4Omen (Diskussion) 22:05, 6. Dez. 2013 (CET)

Verständlichkeit, C-Beispielcode

Wer soll denn das verstehen?

Ich bilde mir ja ganz bescheiden ein, einigermaßen fit in C und Mathematik zu sein und irre jetzt auch nicht gerade als Anfänger durch meine Algorithmen und Datenstrukturen. Aber ich habe heftigste Probleme, den Kauderwelsch, der sich durch die Beispielcodeschnippsel schlängelt, einigermaßen sinnvoll zusammenzulesen.

1. Die Benennung der RB-Forderung R und die des Löschsubjektes R ist ziemlich (unnötig) verwirrend.
2. Die Benennung der Forderung N und des Knotens N auch. Da hilft auch der formal korrekt-verschiedene Satz in Fettdruck und TeX dem Leser nicht wirklich.
3. Warum erläutert man so eine Datenstruktur grad an einem so durchoptimierten Beispielcode? Gut, man hättes noch in Assembler formulieren können. Da muss ich mit etwas fachlichem Hintergrund ja schon zehnmal hinschauen, bis ich überhaupt die zugrundeliegenden Operationen im Code wiedererkenne. Der Zugrif auf die Kindknoten (LEFT+RIGHT-d) ätzt ganz fürchterlich.
4. Dafür dann aber stilistisch fragwürdige Dinger, wie return direkt am Ende einer Funktion.
5. Im Beispiel zum Einfügen-Fall-2 wird der Onkel von N per U = G->child[LEFT+RIGHT-d]; ermittelt, wobei d aber die Kindrichtung von N zum Elter von N ist. Hat also garnix mit dem Onkel zu tun, denn dort wäre die Kindrichtung vom Elter von N zum Großelter von N relevant. Möglicherweise ist da was wegkopiert worden oder ich steh grad auf dem Schlauch.
6. Beim Einfügen-Code sind die NIL-Knoten als Nullzeiger implementiert, was weiter oben auch erläutert und legitimiert wird (knotenorientierte Speicherung). Beim Löschen wird dann der Funktion RBdelete1 ein NIL-Knoten als Argument übergeben. Das steht sich irgendwie diametral entgegen, denn es würde ja nach dieser Forderung NULL übergeben.
7. Was ist denn ein echtes Kind?

Ich versuche noch, den Beispielcode und die Beschreibung zusammen zu verstehen... --Sven Pauli (Diskussion) 13:18, 21. Dez. 2018 (CET)

Ich zeichne hochgradig verantwortlich für die angeführten Mängel (und habe mir erlaubt, sie durchzunummerieren).

Zu 1 und 2: Zusätzlich zum Zusatz Forderung habe ich jetzt längere Mnemonics mit besseren Assoziationen angegeben.

Zu 3: Wenn im Code d die zwei Werte LEFT und RIGHT annehmen kann, sollte die Ausführung der Berechnung LEFT+RIGHT-d nicht allzu große Schwierigkeiten machen. Ich habe eine Bemerkung in den Text, dass nicht-d dasselbe meint.

Zu 4: Dass man direkt am Ende einer Funktion return weglassen kann, weiß vllt nicht jeder. Es ist mit Sicherheit deutlicher, wenn man es nicht weglässt.

Zu 5: Das ist ein eklatanter Fehler. Da man U sehr früh braucht, muss seine Kindesrichtung sogar vor d erhoben werden.

Zu 6: Richtig: Bei Eintritt in RBdelete1 ist N ein NIL-Knoten, in der vorgeschlagenen Implementierung NULL. Aber, wenn ich recht sehe, wird dieses N nicht als Zeiger verwendet.

Zu 7: Ein echtes Kind ist ein Kind, das nicht NIL-Knoten ist.

Auf jeden Fall vielen Dank fürs Durchlesen und für die Anregungen. Ich habe versucht, einen Großteil der Fehler gleich rauszumachen, und dabei noch ein paar andere Sachen gesehen. --Nomen4Omen (Diskussion) 19:52, 21. Dez. 2018 (CET)

Hi Nomen, ich kommentiere einfach mal weiter:

Zu 1. und 2. Magst du die neuen Bezeichnungen weiter in die Erklärungen einbauen? Nicht, dass wir versehentlich konkurrent bearbeiten...

Zu 3. Jetzt stell dir aber mal einen nicht-so-erfahrenen-Programmierer vor, der angesichts der eckigen Klammern nun anfängt, sich das Hirn über Vektoren zu zerbrechen, weil er das nicht direkt durchschaut. Ich denke einfach, das ist für einen Lexikon-Artikel einfach zu viel. Kann man in der Implementierung später sicher so machen und ist auch elegant.

Zu 4. Naja, du erwartest dass jemand die Sache von (3.) durchschaut, glaubst aber gleichzeitig, dass er dann sowas nicht weiß? Ich würds definitiv weglassen, und vermutlich auch alle C-Programmierer, die du fragen wirst. Denn es macht die Sache eigentlich sogar wieder undeutlicher, denn man fragt sich, warum da so ein unnötiges return steht: Verrutscht? Was vergessen?

Zu 5. Dann hab ichs ja doch einigermaßen verstanden, freut mich.

Zu 6. Bist du ganz sicher, dass das korrekt übernommen wurde? Ein Löschalgorithmus, der nur Knoten ohne Kinder löschen kann, ist ziemlich sinnbefreit :) Wenn ichs recht verstehe, soll N nicht ein NIL-Knoten sein, sondern das eine Kind von R, denn R hat ja nur ein Kind (oder keines).

Beste Grüße! --Sven Pauli (Diskussion) 08:25, 22. Dez. 2018 (CET)

Noch etwas macht mich stutzig, und zwar im Löschen-Fall 1: Dort wird rotiert und dann wird S neu zugewiesen, denn das würde ja wegen der Rotation sonst nicht mehr stimmen. Das neue S ist nämlich jetzt C. Aber ich denke, dass S->child[d] da verkehrt ist, denn nach der Rotation hat S ja P und D als Kinder. Entweder müsste man die Zuweisung vor der Rotation machen oder man müsste das neue Geschwister aus P ableiten, oder? --Sven Pauli (Diskussion) 09:28, 22. Dez. 2018 (CET)

Zu 1 und 2: Noch einmal eine neue, jetzt 2-buchstabige Variante.

Zu 3: Fußnote zu "nicht-d ≡ LEFT+RIGHT-d" eingefügt. Allerdings keine Bemerkung, dass die eckigen Klammern nichts mit Vektorräumen zu tun haben. (Sie dienen nur der Indizierung :::: im 2-elementigen Feld child.)

Zu 6: Ich hab's deutlicher gemacht, dass RBdelete2 nur den nicht-so-trivialen Teil des Löschalgorithmus ausmachen soll, und N zum Nicht-Argument degradiert.

Zu 8: War wirklich unnötig umständlich und vllt sogar falsch.

Also allemal vielen Dank für die Mitarbeit, beste Grüße und frohes Fest! --Nomen4Omen (Diskussion) 10:42, 22. Dez. 2018 (CET)

Zu 6 nochmal: Wie gesagt, ich bin mir nach wie vor unsicher, ob N tatsächlich ein Nil-Knoten sein soll. Dann ersetzt du ganz oben in RBdelete2 nämlich schon R durch Nil, egal was noch an R drahnhing. Damit hängst du also genau das eine echte Kind von R ab und fügst es auch nirgendwo wieder ein... --Sven Pauli (Diskussion) 12:56, 22. Dez. 2018 (CET)

Zu 6: Beim "komplizierteren" Fall (R und sein Kind N beide schwarz) hängt gemäß Beobachtung 2 nichts außer NIL-Knoten an R. Denn die Anzahl e echter Kinder von R ist konstruktionsgemäß ≤ 1. Da aber das letzte möglicherweise echte Kind schwarz ist, ist es auch nicht echt, denn sonst müsste es 2 NIL-Kinder haben, womit die Forderung BH verletzt wäre. Also ist e=0.
Die einfachen Fälle möchte ich aber nicht so ausführlich behandeln – die sind also nicht drin in RBdelete2. Um das besser herauszubringen, habe ich die Operationen hochgestuft, damit ich beim Löschen eine weitere Überschriftenebene gewinne, die ich zur Unterscheidung von "Einfache Fälle" und "Der Fall, dass R und N beide schwarz sind" brauche. Hoffentlich kommt das jetzt raus. (Natürlich könnte man auch die "Einfache Fälle" in RBdelete bringen, dann müsste man aber auch die Hibbard-Vorgehensweise bringen, und das möchte ich mir gerne ersparen.) --Nomen4Omen (Diskussion) 18:56, 22. Dez. 2018 (CET)

Hm. Die Beobachtung ist ja richtig. Aber dann könntest du den Code weiter zusammenhauen. So wie er da aktuell geschrieben ist, behandelt er nämlich auch den letzten der einfachen Fälle korrekt. Genaugenommen behandelt er also generisch das löschen eines schwarzen Knotens mit einem Kind. Die Forderung, dass N immer ein Nil-Kind sein muss, ist eigentlich grundlos. Ich glaube, daran habe ich nun die meiste Zeit herumgerätselt... Vielleicht sollte man es in einem Halbsatz erwähnen.

Blöd ist aber, dass der Löschen-Code (im Gegensatz zum Einfügen-Code) allerdings keine NULL-Zeiger verträgt, sondern echte Nil-Kindknoten braucht! Im Löschen-Fall 1 wird beispeilsweise geschaut, ob die beiden Kinder des nahen Neffen schwarz sind (S->child[d]->color == BLACK). Der nahe Neffe kann aber durchaus kinderlos (d.h. NIL) sein, wodurch S->child[d] ein NULL-Zeiger ist, und dann knallts. Das gleiche gibts im Löschen-Fall 2 nochmal, und im Löschen-Fall 4 nochmal für den entfernten Neffen. --Sven Pauli (Diskussion) 21:45, 22. Dez. 2018 (CET)

Du hast glaubich Recht. S->child[d] ist der nahe Neffe, und der hat wie alle Neffen die gleiche Schwarztiefe wie N. Wenn letzterer ein NIL-Knoten ist, dann sind es auch die Neffen. Das gilt für die Löschen-Fälle 1, 2, 4 und 5.

Da sehe ich 3 Möglichkeiten:

1. Vor die Farb-Abfragen werden Abfragen auf == NULL geschaltet. Das muss auch bei den Rotationen gemacht werden.
2. Man zieht die erste Iteration aus der Schleife heraus. Dort und nur dort sind die Knoten N, C, D NIL, und die Farb-Abfragen können bei diesen Knoten völlig entfallen. Bei den höheren Iterationen sind sie alle echte Knoten. Dieses Wissen kann man auch bei den Rotationen ausnützen und ist sicherlich die effizienteste Lösung, sowohl bei Laufzeit wie bei Speicher.
3. Dein Vorschlag: Man implementiert die NIL-Knoten als echte Knoten. Vom Aufschreiben her wohl das Kürzeste.

Das mache ich aber heute nicht mehr. --Nomen4Omen (Diskussion) 22:53, 22. Dez. 2018 (CET)

Drei Abfragen in RBdelete2 auf ==NULL müssten reichen. In der Rotation kommen dann nochmal zwei hinzu, eine für jede Richtung beim Eintragen des Elters weil der nahe Neffe des Rotationspunktes NULL sein könnte. --Sven Pauli (Diskussion) 07:06, 23. Dez. 2018 (CET)

Ich habe mir mal die (nicht allzu große) Mühe gemacht, den Vorschlag 2 einzubringen. Das Ergebnis gefällt mir eigentlich (trotz der bewusst in Kauf genommenen Redundanz) recht gut. In der Tat ergeben sich gegenüber den anderen Vorschlägen beachtliche Einsparungen. Ferner habe ich die Fälle 3 bis 5, die return; machen, aus der Schleife raus. Dadurch fällt das continue; weg, weil es kurzgeschlossen wird. Was mir auch gut gefällt, ist, dass auf ganz natürliche Weise aus do { ... } while() ein do while() { ... } wird (und dabei zugegebenermaßen relativ kleine) Duplizitäten wegfallen.

Die Verlängerung des Artikels beträgt übrigens weniger als 6 %.

Nach meiner Erfahrung muss ich aber damit rechnen, dass der Vorschlag so nicht fehlerfrei dasteht.

--Nomen4Omen (Diskussion) 15:34, 23. Dez. 2018 (CET)

Tut er nicht :) Eine do-while-Schleife gibts nicht in C, das do ist zu viel. Ich meine allerdings auch immer weniger, dass der Artikel sich sinnvoll entwickelt - mit ein Grund, warum ich auch nicht selbst schon etwas bearbeitet habe, auch weil ich dich angesichts deiner vielen Beiträge in diesem Artikel nicht übergehen wollte.

Der Code ist mittlerweile (war ja eingangs auch mein Hauptkritikpunkt) ein fürchterlich verzweigtes und zerrupftes, durchoptimiertes Stück Code. Der ist in diesem Zustand m.M.n. völlig ungeeignet, um den Algorithmus auch nur annähernd verständlich zu erklären :-/ Anstelle der fünf Fälle, die es (nach Abzug der Trivialfälle) noch zu behandeln gäbe, steht da jetzt ein undurchsichtiges Stück Code gespickt mit implizierten Bedingungen, die schon jetzt so unübersichtlich sind, dass du selbst sie mit Kommentaren dazugeschrieben hast... Wie gesagt, ohne deinen Einsatz schmälern zu wollen, frage ich mich aber schon, ob z.B. die Herangehensweise aus dem englischen Artikel hier nicht angebrachter wäre. --Sven Pauli (Diskussion) 13:36, 24. Dez. 2018 (CET)

OK, du bist dran. (Das wäre wohl [3.] Dein Vorschlag: Man implementiert die NIL-Knoten als echte Knoten. Vom Aufschreiben her wohl das Kürzeste.) --Nomen4Omen (Diskussion) 08:36, 25. Dez. 2018 (CET)

Sorry, ich hänge noch eine (mE deutliche) Verbesserung rein, bei der case_1 und case_2 vertauscht sind. --Nomen4Omen (Diskussion) 11:08, 25. Dez. 2018 (CET)

Ich habe gerade den enwiki-Artikel bei Insert und Delete etwas genauer angeschaut und den Eindruck gewonnen, dass

1. der C-Code keineswegs die NIL-Knoten als Rot-Schwarz-Knoten implementiert
2. beim Insert ein unerklärtes LEAF vorkommt, bei Delete jedoch nicht
3. dass es in der Beschreibung von Delete viele Zusatzbemerkungen (Notes: 1. »every null leaf to remain a leaf after all« 2. »is a null leaf and we do not want to represent null leaves as actual node objects, we can ...«) gibt, die ich in ihrer Tiefe nicht völlig verstanden habe
4. ...

Da taucht doch fast die Frage auf, ob Dein Anliegen der »Verständlichkeit« nicht am allerbesten durch totales Weglassen des C-Codes erreicht werden kann. Denn mir scheint, dass jeder Code, ob C oder sonstwas, beim Delete notwendigerweise nicht simpel sein kann.
Die Erläuterungen in Fließtext erklären doch zumindest das Prinzip. --Nomen4Omen (Diskussion) 11:10, 27. Dez. 2018 (CET)

Nach mehr als einer Woche Abwarten auf eine Reaktion von dir, bringe ich eine neue Version. Du kannst ja immer noch dein Anliegen bringen. Gutes Neues Jahr und beste Grüße --Nomen4Omen (Diskussion) 14:16, 1. Jan. 2019 (CET)

Entschuldige, ich hatte zwischen den Jahren PC-freie Zeit - ein frohes Neues ebenfalls!

Der Code auf enwiki muss die NIL-Knoten als nicht-NULL implementieren, sonst ginge replace_node gleich zu Beginn schon in die Hose. Im Begleittext steht es ja auch nochmal (»assume that null leaves are represented by actual node objects rather than NULL«). Das LEAF kam wohl im September 2017 da herein, es soll wohl NULL sein. Insgesamt fällt mir die Thematik ebenfalls ziemlich schwer, ich arbeite immer noch an einer Implementierung, die ich verstehe... --Sven Pauli (Diskussion) 19:38, 3. Jan. 2019 (CET)

@Sven Pauli: Ich habe mir Ben Pfaff genauer angesehen und gefunden, dass er ganz ohne NIL-Knoten auskommt (auch in der Erklärung). Im Ergebnis, das ich gleichzeitig vorstelle, muss man mE weniger rumeiern. Das Ergebnis als C-Code ist natürlich identisch (zu meinem bisherigen Vorschlag). --Nomen4Omen (Diskussion) 12:43, 7. Jan. 2019 (CET)

@Sven Pauli: Zu Deinem letzten Beitrag:

1. Ich habe sowohl im de- wie im en-Artikel Einiges rumgemacht. Ganz wichtig war mit (in beiden Fällen) das Herausarbeiten der Möglichkeit, mit einem einzigen Wert für die Adresse des NIL-Knotens auszukommen, obwohl dieser Wert an vielen Stellen steht. Das ist bei einem Wächterknoten fast noch wichtiger, denn bei multiplen individuellen Wächterknoten geht der Laufzeitgewinn exponentiell flöten.
2. Insbesondere im alten en-Artikel bis Jan 2021 kommen sehr uneinheitlich sowohl Vorschläge "null leaves as actual node objects" (bei replace_node) wie auch NULL (etwas später) vor. So auch der merkwürdige Satz "unlike normal binary search trees, red–black trees can have leaf nodes anywhere". (Die dadurch erzeugte Verwirrung schlägt sich in diesen, aber auch in den it-Artikel hinein.)
   Im neuen de- und en-Artikel habe ich NIL als die Konstante definiert, die in einem Knoten das Pfadende angibt, und es dem Programmierer überlässt, ob als NULL oder ->Sentinel.
   Ferner habe ich herauszuarbeiten versucht, dass die Sehnsucht nach individuellen NIL-Knoten nicht vom Adresswert (NULL oder ->Sentinel), sondern vom Ort kommt, wo dieser Wert steht. (Das ist am heftigsten beim Löschen in der ersten Iteration, wo dieser NIL-Wert den zu löschenden Knoten ersetzt – und man doch die ganze Nachbarschaft genau angucken muss.) Dieser Ort hat Individualität, indem er Elter, Geschwister und Neffen definiert. Und es kommt in der Informatik nicht oft vor, dass der Ort so viel wichtiger ist als der Wert. Ich hoffe sehr, dass das gut genug herauskommt und bitte ggf. um Verbesserungsvorschläge.
3. Ich habe die rekursiven Aufrufe alle raus, so dass es jetzt eine Schleife im INSERT und eine im DELETE gibt, bei der jeweils ganz klar herauskommt, unter welchen Bedingungen wirklich iteriert wird. Damit lässt sich auch die Anzahl der Rotationen besser überblicken. Aber es kann natürlich schon sein, dass der C-Code etwas sophistisch geworden ist. –Nomen4Omen (Diskussion) 21:13, 29. Mär. 2021 (CEST)

C-Code invalid

Das C Beispiel unter "Datenstruktur" in diesem Artikel ist leider falsch; in C existieren weder ein Datentyp bool, noch true und false. Vielleicht wäre es valider C++ Code, da kenne ich mich nicht aus.

Für C sollten false=0, true=1 und color ein int/short/byte sein. -Benutzer:KillPinguin 20:10, 26. Jun. 2019 (nicht signierter Beitrag von Nomen4Omen (Diskussion | Beiträge) 16:34, 29. Mär. 2021 (CEST))