3 ms·
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 implemente
by jey 19y ago
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.)
- thomasptacek 19y agoWhat a silly argument. (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.
- portLAN 19y agolibavl. Next?
- thomasptacek 19y agoEww. Better to use C++ than AVL trees.
- portLAN 19y agohttp://www.stanford.edu/~blp/avl/ http://www.stanford.edu/~blp/avl/ * Binary search trees * AVL trees * Red-black trees
- thomasptacek 19y agoOh. This is a library under straight GPL. You can't use it in non-GPL code. No wonder I hadn't heard of it before. 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.