×

zbMATH — the first resource for mathematics

Skip lists - some results on a recent data structure. (English) Zbl 0855.68022
Summary: The skip list is a list-based data structure introduced some years ago by Pugh. In a joint work with Martinez and Prodinger, the author has investigated an optimized version of the skip list search algorithm and derived an asymptotic result on the variance of the total unsuccessful search cost. Here we give the precise asymptotics for the difference of the variance of this parameter and the variance of the total successful search cost.
MSC:
68P05 Data structures
Keywords:
skip list
PDF BibTeX XML Cite
Full Text: EMIS EuDML