...

/

Discussion on Skiplists

Discussion on Skiplists

Discover more aspects regarding skiplists.

We'll cover the following...

Skiplists were introduced by PughW. Pugh. Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6):668–676, 1990. who also presented a number of applications and extensions of skiplistsW. Pugh. A skip list cookbook. Technical report, Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland, College Park, 1989.. Since then they have been studied extensively. Several researchers have done very precise analysesP. Kirschenhofer, C. Martinez, and H. Prodinger. Analysis of an optimized search algorithm for skip lists. Theoretical Computer Science, 144:199–220, 1995. of the expected length and variance of the length of the ...