My current favourite balanced tree is the treap:<p><a href="http://en.wikipedia.org/wiki/Treap" rel="nofollow">http://en.wikipedia.org/wiki/Treap</a><p>In a treap the shape of the tree is uniquely determined by it being heap-ordered according to a random number associated with each node, in addition to the standard search tree ordering.<p>The various operations are fast and simple to implement. For example, deletion is as simple as rotating the node in question down until it is a leaf, then removing it. The rotations only need to preserve heap ordering, a much simpler invariant than the red/black one.<p>The standard description of the treap calls for a field in each node containing a random number, but you can eliminate that by just hashing the address of the node. That's what I did in GSequence in glib (<a href="http://git.gnome.org/browse/glib/tree/glib/gsequence.c" rel="nofollow">http://git.gnome.org/browse/glib/tree/glib/gsequence.c</a>).
Wouldn't it be more profitable, in terms of real-world performance, to adapt B-trees to maximize locality in CPU data caches? (One could also apply stochastic optimization to a B-tree based algorithm to reduce the number of operations on delete.)