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


One thought on “Red black tree resources and sources

Comments are closed.