Some observations on skip-lists. (English) Zbl 0735.68018

Summary: The skip-list data-structure was proposed by W. Pugh [A skip list cookbook, UMIACS-TR-89-72.1, University of Maryland], [Skip list: A probabilistic alternative to balanced trees, Commun. ACM 33, No. 6, 668- 676 (1990)] as an alternate to balanced binary search trees. This remarkably simple data-structure uses randomization and W. Pugh (loc. cit.) proved that the expected performance is comparable to the balanced trees. We prove that the performance can be further guaranteed in the following sense: the probability of the search time or space complexity exceeding their expected values, approaches 0 rapidly as the number of keys increases.


68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Angluin, D.; Valiant, L., Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. Comput. System Sci., 18 (1979) · Zbl 0437.05040
[2] Aragon, C.; Seidel, R., Randomized search trees, Proc. 30th Ann. Sympos. on Foundations of Computer Science, 540-545 (1989)
[3] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statist., 23, 493-507 (1952) · Zbl 0048.11804
[5] Pugh, W., Skip lists: A probabilistic alternative to balanced trees, Comm. ACM, 33, 6, 668-676 (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.