A skip list is a probabilistic alternative to binary trees. They seem to be a smart and efficient way of achieving a similar objective, i.e. doing what binary trees are good at.

See ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

SkipList seen in the wild. GrayWatson's Dmalloc Debug Malloc library http://dmalloc.com/ uses a SkipList internally (in chunk.c) to maintain its free and allocated memory block lists sorted by the size of the memory block in bytes.

----
CategoryDataStructure