Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
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
@FrustratedWithFormsDesigner What does WAG mean? – Maxpm Oct 27 '11 at 21:20
@Maxpm: wild a--ed guess. Personally I think it was roulette inspired. – Wyatt Barnett Oct 27 '11 at 22:04
@FrustratedWithFormsDesigner - Nice guess, turned out to be totally on the money. – Slomojo Oct 27 '11 at 23:53
up vote 78 down vote accepted

EDIT: Answer from Professor Guibas:

from Leonidas Guibas to of the "Red-Black" term mailed-by 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.

share|improve this answer
I have just emailed Professor Guibas. Let's see if we can get a definitive response. – Dan McGrath Oct 27 '11 at 22:09
+1 For resourcefulness. – NickC Oct 28 '11 at 0:43
I wonder if there are any extant copies of the original trees... :) – Porges Jan 12 '12 at 0:38
This is exactly how this site is supposed to work, bravo. – David Cowden Dec 18 '13 at 22:09
This doesn't match with statement by co-inventor of RB-Trees. Somebody better clear this up :). See my answer. – ShitalShah 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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