45

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.

8
  • 16
    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
  • 4
    @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
90

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.

4
  • 25
    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
  • 2
    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
7

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.

2
  • 2
    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
  • I agree it's hard to buy that color laser printing existed at PARC in 1978 and color laser printers didn't ship until 1994. On the other hand the first color copier appeared in 1973 so it's not impossible. It would just be yet another place where Xerox failed to ship. On the other hand non laser color printers existed in 1977. – gman Jan 13 at 4:03
0

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.

Refer here.

4
  • this seems to merely repeat top and second top answers that were posted many years before – gnat Apr 10 '20 at 12:07
  • I believe the printer reference hasn't been mentioned explicitly while it's considered a good source for the name, hence I added that. I mention the drawing pens and point to the original answer only for completeness. – krishnakeshan Apr 10 '20 at 13:17
  • per my reading, second top answer posted about 5 years ago explicitly mentions this: "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" – gnat Apr 10 '20 at 13:19
  • That quote is from a Coursera course, and the printer is mentioned way down so someone might miss it? I've also provided a Wikipedia reference for something more accessible to everyone. Will take down the answer if it violates anything tho, please let me know. – krishnakeshan Apr 10 '20 at 13:24

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