I've been receiving quite a few messages at work along the lines of "What are
skip lists?"

The classic reference for skip lists is "Skip Lists: A Probabilistic Alternative
to Balanced Trees," by William Pugh, CACM June 1990 (Vol 3 No 6).  Reading this
reference is much better than asking me, because I am unbelievably busy at the
moment and just won't have time to provide a decent answer to you.

Quoting:

"Skip lists are a probabilistic alternative to balanced trees. Skip lists are
balanced by consulting a random number generator. Although skip lists have bad
worst-case performance, no input sequence consistently produces the worst-case
performance (much like quicksort when the pivot element is chosen randomly). [...]

"It is easier to balance a data structure probabilistically than to explicity
maintain the balance.  For many applications, skip lists are a more natural
representation than trees, and they lead to simpler algorithms. The simplicity
of skip list algorithms makes them easier to implement and provides significant
constant factor speed improvements over balanced tree and self-adjusting tree
algorithms.  Skip lists are also very space efficient [....]"

There you go.  Now, back to our regularly scheduled topic.

=============== O Fortuna, velut Luna, statu variabilis ===============
uunet!joebloe!joseph   (602) 732-2549 day   joseph%joebloe@uunet.uu.net
1400 N Alma School                #163               Chandler, AZ 85224
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
           Be hip!  Support comp.sys.mac.programmer.moof!