OK, then I want you to write me an efficient implementation of Red-Black tree deletion, and do it within an hour.
(std::map and std::set are usually implemented with a Red-Black tree.)
(std::map and std::set are usually implemented with a Red-Black tree.)
(a) STL's map and set weren't implemented in an hour.
(b) Abstract data types (and, more generally, code libraries) predate C++ by decades.
Six years ago, I took over as lead dev for a product now counting and statistically modeling a significant percentage of all the packets traveling across the backbones of virtually every tier 1 ISP in the world. One of the first things I did there, coming off 3 years of C++ development, was to backport the STLport Red-Black tree, from the "map" template to an "rbtree.c" library.
My rbtree.c is faster than STLport's, and far easier to use. You don't need to read Meyers and keep a cheat sheet to avoid iterator invalidation to use it.
* Binary search trees
* AVL trees
* Red-black trees
Thanks for the pointer, it's neat. I really like how my approach turned out; the STLport red-black tree is well done. Backporting it to C only took a couple hours.