Search⌘ K
Home
Courses
Data Structures with Generic Types in C++

Discussion on Skiplists

Explore the design and analysis of skiplists as a data structure that offers efficient search, insertion, and deletion through probabilistic balancing. Understand their applications, variations, and real-world use cases in software systems including databases and operating systems.

We'll cover the following...

Additional notes

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 ...