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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
EDIT: Answer from Professor Guibas:
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: