Uma Árvore vermelha / preta é uma maneira de implementar uma árvore de pesquisa binária balanceada. Os princípios por trás de como isso funciona fazem sentido para mim, mas as cores escolhidas não. Por que vermelho e preto, ao contrário de qualquer outro par de cores ou de atributos em geral? Quando ouço "vermelho e preto", as primeiras coisas que vêm à mente são xadrez e Os Miseráveis, nenhum dos que parece particularmente aplicável neste contexto.
EDIT : Resposta do professor Guibas:
from Leonidas Guibas [email protected] to of the "Red-Black" term mailed-by cs.stanford.edu hide details 16:16 (0 minutes ago)
we had red and black pens for drawing the trees.
Eu acredito que o termo apareceu pela primeira vez em " Uma estrutura dicromática para árvores balanceadas " de Leonidas J. Guibas e Robert Sedgewick em 1978.
No Coursera, BSTs Red-Black (2012) , Robert Sedgewick diz o seguinte:
A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC which was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, ethernet and object-oriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that’s why we picked the color red to distinguish red links, the types of links, in three nodes. So, that’s an answer to the question for people that have been asking.
Tags history data-structures