Average search and update costs in skip lists

DOI10.1007/BF01994884zbMath0761.68030OpenAlexW2044253986MaRDI QIDQ1196460

Patricio V. Poblete, Thomas Papadakis, J. Ian Munro

Publication date: 14 December 1992

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01994884

zbMATH Keywords

probabilistic algorithmsdictionarySkip lists

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (9)

The binomial transform and the analysis of skip lists ⋮ The number of distinct values in a geometrically distributed sample ⋮ Combinatorics of geometrically distributed random variables: Left-to-right maxima ⋮ The binomial transform and its application to the analysis of skip lists ⋮ Combinatorics of geometrically distributed random variables: Run statistics ⋮ Zip-zip trees: making zip trees more balanced, biased, compact, or persistent ⋮ Skip trees, an alternative data structure to skip lists in a concurrent approach ⋮ Analysis of an optimized search algorithm for skip lists ⋮ Gap-free compositions and gap-free samples of geometric random variables

Cites Work

• Unnamed Item
• Unnamed Item
• Analysis of the standard deletion algorithms in exact fit domain binary search trees
• A limit theory for random skip lists
• Randomized search trees

This page was built for publication: Average search and update costs in skip lists