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).
Original paper: http://user.it.uu.se/~arnea/ps/simp.pdf
Tutorial giving intuition for this data structure: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_t...
: http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf (2009)
: http://www.cs.princeton.edu/~sssix/papers/ravl-trees.pdf (2010)