OMG. I have yet to see a working implementation of 'delete' from Sedgewick. Further, a repaired delete (from the description on the slides) will rotate back a

OMG. I have yet to see a working implementation of 'delete' from Sedgewick. Further, a repaired delete (from the description on the slides) will rotate back an forth horribly. Awful stuff, awful reasoning. Symmetric RB trees are similarly compact when implemented using a direction flag to abstract away the symmetry. A good (and working!) implementation for a top-down no-parent pointer RB tree is by Julienne Walker: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_t.... No back-and-forth rotations here. Very good explanations and very good code. Or use AVL trees instead, they work naturally (i.e., without clever restructuring) more cache-locally by storing the balance info one node up the tree.