by James Chapman on May 7, 2011.
Tagged as: Lunches.
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.