Analysis of an optimized search algorithm for skip lists

DOI10.1016/0304-3975(94)00296-UMaRDI QIDQ672990zbMATH OpenDBLPWikidataFDO

Authors Peter Kirschenhofer, Conrado Martínez, Helmut Prodinger

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

skip list search algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Analysis of the expected search cost in skip lists
• Average search and update costs in skip lists
• Skip lists - some results on a recent data structure
• Analysis of a new skip list variant

Cites work

• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• A design of a parallel dictionary using skip lists
• A limit theory for random skip lists
• Average search and update costs in skip lists
• Combinatorics of geometrically distributed random variables: Left-to-right maxima
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• On a tree collision resolution algorithm in presence of capture

Cited in

(3)

• Analysis of the expected search cost in skip lists
• A design of a parallel dictionary using skip lists
• Analysis of a new skip list variant

This page was built for publication: Analysis of an optimized search algorithm for skip lists

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672990)