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:
- 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)