Red-Black Trees - Curious Name Origins

This is old news, I guess, but it was new to me.

The colors "red" and "black" were chosen for the red-black tree data structure because of laser printer capabilities at the time, coupled with the taste of the researchers studying it (Leonidas Guibus and R. Sedgewick).

Also Sprach Wikipedia:

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.

Robert Sedgewick, from Coursera, as cited in Wikipedia

And btw, Sedgewick continues his affection for red and black to this day in his classic Algorithms textbook.

Popular Posts