Skip lists: a probabilistic alternative to balanced trees
- 1 June 1990
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 33 (6) , 668-676
- https://doi.org/10.1145/78973.78977
Abstract
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.Keywords
This publication has 5 references indexed in Scilit:
- Slow optimally balanced search strategies vs. cached fast uniformly balanced search strategiesInformation Processing Letters, 1990
- Incremental computation via function cachingPublished by Association for Computing Machinery (ACM) ,1989
- Randomized search treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Self-adjusting binary search treesJournal of the ACM, 1985
- Randomly balanced binary treesCalcolo, 1980