skiplist

http://tcllib.sourceforge.net/doc/skiplist.html
The skiplist package is a member of the struct module of tcllib.

It creates an alternative data structure to binary trees.

To quote the inventor of skip lists, William Pugh:

Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

For more details on how skip lists work, see Pugh, William. Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676. Also, see ftp://ftp.cs.umd.edu/pub/skipLists/

For a visual demonstrations on how skiplists work, see SkipList Demo.