De onde vem o termo "Árvore Vermelha / Preta"?

42

Uma Árvore Vermelha / Preta é uma maneira de implementar uma árvore de pesquisa binária equilibrada. Os princípios por trás de como funciona fazem sentido para mim, mas as cores escolhidas não. Por que vermelho e preto, em oposição a qualquer outro par de cores ou atributos em geral? Quando ouço "vermelho e preto", as primeiras coisas que me vêm à mente são os tabuleiros de damas e Les Misérables, nenhuma das quais parece particularmente aplicável neste contexto.

data-structures history Mason Wheeler
fonte
14
WAG: canetas BIC são frequentemente vendidas em embalagens contendo uma mistura de azul, preto e vermelho (esqueço em que proporções). Usar azul e preto no mesmo diagrama em um pedaço de papel pode dificultar a leitura. Portanto, se o diagramador preferir o preto ao vermelho, provavelmente trocará a caneta azul pelo vermelho. Ou pelo menos é assim que seria se fosse eu ... Não tenho idéia de nenhum motivo real , mas especular com certeza é divertido! Talvez possamos até começar uma lenda urbana dessa maneira!
FrustratedWithFormsDesigner
4
Eu tinha um professor de ciência da computação, que afirmou que as cores foram escolhidas para representar convenções típicas de cor fio para ânodo (vermelho, +) e do cátodo (preto, -)
holtavolt
1
@FrustratedWithFormsDesigner O que significa o WAG ?
Maxpm 27/10/11
3
@ Maxpm: palpite selvagem. Pessoalmente, acho que foi inspirado na roleta.
Wyatt Barnett
4
@FrustratedWithFormsDesigner - Bom palpite, acabou por ser totalmente sobre o dinheiro.
ocodo 27/10

Respostas:

86

EDIT : Resposta do Professor Guibas:

Leonidas Guibas [email protected] para o termo "Vermelho-Preto" enviado por cs.stanford.edu ocultar detalhes 16:16 (1 minuto atrás)

tínhamos canetas vermelhas e pretas para desenhar as árvores.

Acredito que o termo apareceu pela primeira vez em "Uma estrutura dicromática para árvores equilibradas" de Leonidas J. Guibas e Robert Sedgewick em 1978.

Dan McGrath
fonte
23
Acabei de enviar um email para o professor Guibas. Vamos ver se podemos obter uma resposta definitiva.
Dan McGrath
2
Gostaria de saber se existem cópias existentes das árvores originais ... :)
porges
1
É exatamente assim que este site deve funcionar, bravo.
precisa
1
Isso não corresponde à declaração do co-inventor da RB-Trees. Alguém melhor esclarecer isso :). Veja minha resposta.
Shital Shah
6

Em Coursera, BSTs Vermelho-Preto (2012) , Robert Sedgewick diz o seguinte:

Muitas pessoas perguntam por que usamos o nome vermelho-preto. Bem, inventamos essa estrutura de dados, essa maneira de observar árvores balanceadas, no Xerox PARC, que era o lar do computador pessoal e muitas outras inovações com as quais vivemos hoje, inserindo interfaces gráficas de usuário, ethernet e programação orientada a objetos. [sic] e muitas outras coisas. Mas uma das coisas que foi inventada lá foi a impressão a laser e ficamos muito empolgados por ter uma impressora a laser colorida nas proximidades, capaz de imprimir as coisas em cores e com as cores que o vermelho parecia melhor. Por isso, escolhemos a cor vermelha para distinguir os links vermelhos, os tipos de links, em três nós. Então, essa é uma resposta para a pergunta das pessoas que têm perguntado.

Shital Shah
fonte
Mesmo no PARC, não encontrei nenhuma referência à impressão a laser em cores em 1978 (quando existe a primeira referência a árvores vermelho-pretas). Por exemplo, o primeiro comercial da HP foi 1994 e não consigo encontrar referências a impressoras a laser coloridas nos anos 80?
Dan McGrath