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.

  • 14
    WAG: BIC pens are often sold in packs containing a mix of blue, black, and red (I forget in what proportions). Using blue and black on the same diagram on a piece of paper might make it hard to read so if the diagrammer prefers black to red, they'd probably swap the blue pen for red. Or at least that's how it would be if it were me... I have no idea about any real reason, but speculating sure is fun! Maybe we can even start an urban legend this way! – FrustratedWithFormsDesigner Oct 27 '11 at 20:52
  • 4
    I had a computer science professor who claimed that the colors were chosen to represent typical wire color conventions for anode (red, +) and cathode (black, -) – holtavolt Oct 27 '11 at 20:53
  • 1
    @FrustratedWithFormsDesigner What does WAG mean? – Maxpm Oct 27 '11 at 21:20
  • 3
    @Maxpm: wild a--ed guess. Personally I think it was roulette inspired. – Wyatt Barnett Oct 27 '11 at 22:04
  • 4
    @FrustratedWithFormsDesigner - Nice guess, turned out to be totally on the money. – ocodo Oct 27 '11 at 23:53

EDIT: Answer from Professor Guibas:

from Leonidas Guibas guibas@cs.stanford.edu 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.

  • 23
    I have just emailed Professor Guibas. Let's see if we can get a definitive response. – Dan McGrath Oct 27 '11 at 22:09
  • 2
    I wonder if there are any extant copies of the original trees... :) – porges Jan 12 '12 at 0:38
  • 1
    This is exactly how this site is supposed to work, bravo. – David Cowden Dec 18 '13 at 22:09
  • 1
    This doesn't match with statement by co-inventor of RB-Trees. Somebody better clear this up :). See my answer. – Shital Shah Sep 2 '15 at 9:07

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.

  • Even at PARC, I cannot find any reference to color Laser Printing in 1978 (when the first reference to Red-Black trees exist). For example, HP's first commercial one was 1994 and I cannot find any references to color laser printers in the 80's? – Dan McGrath Oct 2 '17 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.