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)
One thought on “Red black tree resources and sources”
Comments are closed.