Sen, Sandeep Some observations on skip-lists. (English) Zbl 0735.68018 Inf. Process. Lett. 39, No. 4, 173-176 (1991). 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. Cited in 4 Documents MSC: 68P05 Data structures 68Q25 Analysis of algorithms and problem complexity Keywords:dictionary operations on ordered lists; random sampling PDF BibTeX XML Cite \textit{S. Sen}, Inf. Process. Lett. 39, No. 4, 173--176 (1991; Zbl 0735.68018) Full Text: DOI References: [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.