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.
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.
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 (http://git.gnome.org/browse/glib/tree/glib/gsequence.c).
Other cool balanced trees: rank-balanced trees [1], which have O(1) amortized insertion, deletion, and rebalancing, and ravl trees [2], which do not rebalance on deletion in hopes that insertions will happen soon and seem to rotate fewer times than both red-black trees and rank-balanced trees in experiments.
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.)
http://en.wikipedia.org/wiki/Treap
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.
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.
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 (http://git.gnome.org/browse/glib/tree/glib/gsequence.c).