Red black tree resources and sources

My earlier article about red-black trees seems to have attracted some interest, so I thought I’d do another one just listing some resources.

The most cited text on this issue is Introduction to Algorithms though you don’t need it to implement your own red-black tree. Some useful internet sources are:

This animation gives you a good idea about how your tree should work.

And this video (based on the book) is pretty essential viewing.

Lecture 10: Red-black Trees, Rotations, Insertions, Deletions – Erik Demaine

If you want sources:

My C++ implementation of a red-black tree (GPL licensed)

The C++ standard template library offers various red-black tree based container classes: explained in this Dr Dobb’s Journal article.

The Linux kernel has a C implementation of a red-black tree – read here for more about that. The implementation can be found in the kernel sources at /include/linux/rbtree.h

Related Articles

• Red-black trees (cartesianproduct.wordpress.com)
• Computational Origami by MIT’s Erik Demaine (brainpickings.org)
• Nedtries: an ordered container faster than hash tables and red-black trees (nedprod.com)