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: