D'où vient le terme «arbre rouge / noir»?

42

Un arbre rouge / noir est un moyen d'implémenter un arbre de recherche binaire équilibré. Les principes sous-jacents à son fonctionnement me semblent judicieux, mais pas les couleurs choisies. Pourquoi le rouge et le noir, par opposition à toute autre paire de couleurs ou d'attributs en général? Quand j'entends "rouge et noir", les premières choses qui me viennent à l’esprit sont les damiers et Les Misérables, qui ne semblent pas particulièrement applicables dans ce contexte.

data-structures history Maçon Wheeler
la source
14
WAG: Les stylos BIC sont souvent vendus dans des emballages contenant un mélange de bleu, de noir et de rouge (j'oublie dans quelles proportions). L'utilisation de bleu et de noir sur le même diagramme sur une feuille de papier peut rendre la lecture difficile. Par conséquent, si le diagrammer préfère le noir au rouge, il remplacera probablement le stylo bleu par le rouge. Ou du moins c'est ce qui se passerait si c'était moi ... Je n'ai aucune idée de la vraie raison, mais il est amusant de spéculer, c'est amusant! Peut-être pourrions-nous même créer une légende urbaine de cette façon!
FrustratedWithFormsDesigner
4
Un professeur d’informatique a affirmé que les couleurs avaient été choisies de manière à représenter les conventions de couleurs typiques des fils pour anode (rouge, +) et cathode (noir, -)
holtavolt
1
@FrustratedWithFormsDesigner Que signifie WAG ?
Maxpm
3
@Maxpm: devinette sauvage. Personnellement, je pense que c'était inspiré de la roulette.
Wyatt Barnett
4
@FrustratedWithFormsDesigner - Belle estimation, s'est avéré être totalement sur l'argent.
ocodo

Réponses:

86

EDIT : Réponse du professeur Guibas:

de Leonidas Guibas [email protected] à "Rouge-Noir" terme envoyé par cs.stanford.edu masquer les détails 16:16 (Il y a 0 minute)

nous avions des stylos rouges et noirs pour dessiner les arbres.

Je crois que le terme est apparu pour la première fois dans "Un cadre dichromatique pour les arbres équilibrés" de Leonidas J. Guibas et Robert Sedgewick en 1978.

Dan McGrath
la source
23
Je viens d'envoyer un courriel au professeur Guibas. Voyons si nous pouvons obtenir une réponse définitive.
Dan McGrath
2
Je me demande s’il existe des copies existantes des arbres originaux ... :)
2012
1
C'est exactement comment ce site est censé fonctionner, bravo.
David Cowden
1
Cela ne correspond pas à la déclaration du co-inventeur de RB-Trees. Quelqu'un ferait mieux d'éclaircir ça :). Voir ma réponse.
Shital Shah
6

Dans Coursera, BST rouge-noir (2012) , Robert Sedgewick dit ceci:

Beaucoup de gens se demandent pourquoi nous avons utilisé le nom rouge – noir. Eh bien, nous avons inventé cette structure de données, cette façon de regarder les arbres équilibrés, chez Xerox PARC, qui hébergeait l'ordinateur personnel et de nombreuses autres innovations avec lesquelles nous vivons aujourd'hui, en entrant dans les interfaces utilisateur graphiques, les programmations ethernet et orientées objet. [sic] et beaucoup d'autres choses. Mais l’une des choses inventées a été l’impression laser et nous étions très heureux d’avoir une imprimante laser couleur à proximité capable d’imprimer des choses en couleur et en dehors des couleurs, le rouge semblait être le meilleur. C'est pourquoi nous avons choisi la couleur rouge pour distinguer les liens rouges, les types de liens, en trois nœuds. Donc, c'est une réponse à la question pour les personnes qui l'ont demandé.

Shital Shah
la source
Même au PARC, je ne trouve aucune référence à l’impression laser couleur en 1978 (lorsque la première référence aux arbres rouge-noir existe). Par exemple, le premier commercial HP a été 1994 et je ne trouve aucune référence aux imprimantes laser couleur dans les années 80?
Dan McGrath