Brian C. Dean

Associate Professor
Division of Computer Science
School of Computing, Clemson University

Office: McAdams Hall, Room 205
Phone: 864-656-5866
Mail: Brian C. Dean, School of Computing, Box 340974, Clemson SC 29634-0974

Exploring the Duality Between Skip Lists and Binary Search Trees

with Zachary Jones. Proceedings of the 45th Annual ACM Southeast Regional Conference (ACMSE), pages 395-399, 2007.


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.