Skiplist Demonstration
By David M Howard
Wednesday, August 27, 2003
Skip Lists, first described in "Skip Lists: A Probabilistic Alternative to Balanced Trees", W. Pugh (CACM, June 1990), are an alternative representation of balanced trees (not binary) that provides approximate O(log n) access times with the advantage that the implementation is straightforward and the storage requirement is less than a standard balanced tree structure. A distinct difference from most search structures is that the behavior of skip lists is probabilistic without dependence on the order of insertion of elements. Some characteristics of skip lists are:
- Advantages
- implementation is straightforward and easier than a typical balanced tree algorithm
- storage requirements are less than for typical balanced trees
- insertions and deletions do not require rebalancing
- supports insert,remove,find and join operations (especially useful for symbol table applications)
- Disadvantages
- search time for insert and find is longer than for trees
- depends on a random number generator which can mean difficult debug
Each node in a skip list has an array of several 'forward pointers' that link to nodes further along in the list. The number of forward pointers (node height) in a particular node is determined by a probability function that is applied during insertion, and that serves to create a few 'tall' nodes, more 'medium size' nodes and lots of 'small' nodes. The distribution of the node heights is random.
To search for a key in the skip list, start at the root and work left to right. For the current node, work down from the top of the array of forward pointers.Find the first forward pointer that links to another node. Compare the search key against the key of the forward node. If the keys match, you are done. If the search key is less than the forward node, then the value is on the left side of the forward node, otherwise it is on the right side. If it is on the left side, stay on the current node and go down one to the next forward node and repeat. If the key is on the right side, move to the node that is linked by the forward node, and start over.
It is the probabilistic allocation of forward node arrays as each element is inserted that gives the skip list its performance characteristics. The analysis is not trivial. A good overview is in "Algorithms in C++ Third Edition", Sedgewick, Addison-Wesley 1998. The implementations used here are ported from the C++ implementation in the article "Skip Lists in C++", Bill Whitney, C/C++ Users Journal, November 1998.
The implementation here builds a 32 element skip list with the same input data each time. The resulting skip list is different each time it is built because of the random number generator controlling allocation of forward nodes. You can do the following:
- Build (Fast) - build the skip list quickly so you can get to the find functions
- Build (Slow) - build the skip list slowly so you can see how the insertions work
- Reset - clear and start over with a new skip list structure.
- Find - take the integer value from the adjacent TextField and search the skip list, and get a count of the number of operations required.
- FindAll - enumerate thru the data in the skip list and find each element in succession, and then display the average number of operations required, which should be around log2(32) = 5.
Source Code
