Division of Computer Science
School of Computing, Clemson University
Office: McAdams Hall, Room 205
Mail: Brian C. Dean, School of Computing, Box 340974, Clemson SC 29634-0974
Although skip lists were introduced as an alternative to balanced binary search trees (BSTs), we show that the skip list can be interpreted as a type of randomly-balanced BST whose simplicity and elegance is arguably on par with that of today's most popular BST balancing mechanisms. In this paper, we provide a clear, concise description and analysis of the "BST" interpretation of the skip list, and compare it to similar randomized BST balancing mechanisms. In addition, we show that any rotation-based BST balancing mechanism can be implemented in a simple fashion using a skip list.
Available in pdf and postscript.