Red-black trees

May 7th, 2011 by James Chapman

I explained that a red-black tree is really just a 2-3-4 tree in disguise. I then reviewed Chris Okasaki’s simple, short and elegant treatment of red-black trees (Red-Black Tress in a Functional Setting) which I think is a great example of functional programming and rightly a “functional pearl”. This is interesting stuff I think and not as widely known as it should be.

Further reading:
The correspondence between 2-3-4 trees and red-black trees is made sharper by considering Sedgwick’s Left-Leaning Red-Black Trees. See here for a formalisation in Agda.

One Response to “Red-black trees”

  1. porges Says:

    Just a note: Your second link is borked :)

Leave a Reply