A Red/Black Tree is one way to implement a balanced binary search tree. The principles behind how it works make sense to me, but the chosen colors don't. Why red and black, as opposed to any other pair of colors or of attributes in general? When I hear "red and black," the first things that come to mind are checkerboards and Les Misérables, neither of which seems particularly applicable in this context.
EDIT: Answer from 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.
I believe the term first appeared in "A dichromatic framework for balanced trees" from Leonidas J. Guibas and Robert Sedgewick in 1978.
In Coursera, Red-Black BSTs (2012), Robert Sedgewick says this:
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.
As answered, the creators of the data structure only had red and black pens to draw hence the name red-black trees. According to Wikipedia, in the same article, it also says:
The color "red" was chosen because it was the best-looking color produced by the color laser printer available to the authors while working at Xerox PARC.