Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 32 down vote favorite
6

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
12  
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
3  
@FrustratedWithFormsDesigner - Nice guess, turned out to be totally on the money. – Slomojo Oct 27 '11 at 23:53
show 3 more comments

1 Answer

up vote 61 down vote accepted

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.

share|improve this answer
13  
I have just emailed Professor Guibas. Let's see if we can get a definitive response. – Dan McGrath Oct 27 '11 at 22:09
8  
+1 For resourcefulness. – NickC Oct 28 '11 at 0:43
1  
I wonder if there are any extant copies of the original trees... :) – Porges Jan 12 '12 at 0:38

Your Answer

 
discard

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.