Woher kommt der Begriff „Roter / Schwarzer Baum“?

42

Ein Rot / Schwarz-Baum ist eine Möglichkeit, einen ausgeglichenen binären Suchbaum zu implementieren. Die Prinzipien dahinter machen für mich Sinn, aber die gewählten Farben nicht. Warum rot und schwarz im Gegensatz zu anderen Farbpaaren oder Attributen im Allgemeinen? Wenn ich "rot und schwarz" höre, fallen mir als erstes Schachbrettmuster und Les Misérables ein, die in diesem Zusammenhang beide nicht besonders zutreffen.

Mason Wheeler
quelle
14
WAG: BIC-Stifte werden oft in Packungen mit einer Mischung aus Blau, Schwarz und Rot verkauft (ich vergesse in welchen Anteilen). Die Verwendung von Blau und Schwarz für dasselbe Diagramm auf einem Blatt Papier kann die Lesbarkeit beeinträchtigen. Wenn die Diagrammer Schwarz gegenüber Rot bevorzugt, wird der blaue Stift wahrscheinlich gegen Rot ausgetauscht. Oder zumindest das ist , wie es wäre, wenn es nach mir ginge ... ich keine Ahnung von irgendwelchen haben wirkliche Grund, aber spekulieren sicher ist Spaß! Vielleicht können wir auf diese Weise sogar eine urbane Legende gründen!
FrustratedWithFormsDesigner
4
Ich hatte einen Informatikprofessor, der behauptete, dass die Farben ausgewählt wurden, um typische
Drahtfarbkonventionen
1
@FrustratedWithFormsDesigner Was bedeutet WAG ?
Maxpm
3
@Maxpm: Eine wilde Vermutung. Persönlich denke ich, es war Roulette inspiriert.
Wyatt Barnett
4
@FrustratedWithFormsDesigner - Gut geraten, es stellte sich heraus, dass es voll auf dem Geld liegt.
Ocodo

Antworten:

86

EDIT : Antwort von Professor Guibas:

von Leonidas Guibas [email protected] bis zum von cs.stanford.edu verschickten Begriff "Rot-Schwarz" Details verbergen 16:16 (vor 0 Minuten)

Wir hatten rote und schwarze Stifte zum Zeichnen der Bäume.


Ich glaube, der Begriff tauchte erstmals 1978 in "Ein dichromatischer Rahmen für ausgewogene Bäume" von Leonidas J. Guibas und Robert Sedgewick auf.

Dan McGrath
quelle
23
Ich habe gerade Professor Guibas eine E-Mail geschickt. Mal sehen, ob wir eine definitive Antwort bekommen können.
Dan McGrath
2
Ich frage mich, ob es noch Kopien der ursprünglichen Bäume gibt ... :)
porges
1
Genau so soll diese Seite funktionieren, Bravo.
David Cowden
1
Dies stimmt nicht mit der Aussage des Miterfinders von RB-Trees überein. Jemand sollte das besser klären :). Siehe meine Antwort.
Shital Shah
6

In Coursera, Red-Black BSTs (2012) , sagt Robert Sedgewick Folgendes :

Viele Leute fragen, warum wir den Namen Rot-Schwarz verwendet haben. Nun, wir haben diese Datenstruktur, diese Art der Betrachtung ausgewogener Bäume, in Xerox PARC erfunden, wo sich der Personal Computer und viele andere Innovationen befanden, mit denen wir heute arbeiten, um grafische Benutzeroberflächen, Ethernet und objektorientierte Programmierungen einzugeben und viele andere Dinge. Aber eines der Dinge, die dort erfunden wurden, war das Laserdrucken, und wir waren sehr aufgeregt, einen Farblaserdrucker in der Nähe zu haben, der Dinge in Farbe und in den Farben ausdrucken konnte, bei denen das Rot am besten aussah. Deshalb haben wir die Farbe Rot gewählt, um rote Links, die Arten von Links, in drei Knoten zu unterscheiden. Das ist also eine Antwort auf die Frage für Leute, die gefragt haben.

Shital Shah
quelle
Sogar bei PARC kann ich keinen Hinweis auf Farblaserdruck 1978 finden (wenn der erste Hinweis auf rot-schwarze Bäume vorhanden ist). Zum Beispiel war die erste kommerzielle Version von HP 1994 und ich kann keine Hinweise auf Farblaserdrucker in den 80er Jahren finden?
Dan McGrath