Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Discussion on Skiplists

Understand the concept and significance of skiplists in data structures by exploring their probabilistic approach to balancing. Learn how skiplists provide efficient O log n complexity for search and update operations, examine their variants, and discover their applications in real-world systems like Redis and HP-UX.

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