Skip to content

Why the name red-black tree?

Many explanations are circling the internets, but this one is from the man itself.  Robert Sedgewick, one of the two computer scientists, who published the paper which first used the term red-black tree said this in his Coursera class on algorithms:

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 graphic user interfaces, ethernet and object oriented programmings and many other things. But one of the things that was invented there was laser printing and we were wery 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 tree nodes. So, that’s an answer to the question for people that have been asking.

So there you go, case closed. Unless the other author of the paper will remember things differently.

Enhanced by Zemanta

Categories: Thoughts.

Tags: , , ,

  • A.S

    But what does “red” indicate? What signifies “black”?