Home → Magazine Archive → June 1990 (Vol. 33, No. 6) → Skip lists: a probabilistic alternative to balanced... → Abstract

Skip lists: a probabilistic alternative to balanced trees

By William Pugh

Communications of the ACM, Vol. 33 No. 6, Pages 668-676

Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

The full text of this article is premium content


No entries found