Séminaire Lotharingien de Combinatoire, B33i (1994), 9pp
Peter Kirschenhofer
Skip Lists - Some Results on a Recent Data Structure
Abstract.
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.
The following versions are available: