Related Readings

• Skip Lists: A Probabilistic Alternative to Balanced Trees (local copy)
• Skip Lists - CMSC 420 (local copy)

Notes

Skip list is a probabilistic data structure that is built on top of a standard linked list. It introduces multiple levels. Each level is a linked list on its own. The bottom level is the standard linked list, which contains all elements. Each time we go one level above, the number of elements stored in that level is reduced by half. This essentially transforms the data structure into a tree.

Where does the probabilistic aspect come into play? The problem is that it's expensive to maintain an ideally balanced skip list where level N+1 has exactly half elements of level N. The solution to this problem is to promote a node to a higher level probabilistically. Suppose the bottom level is level 0, then the probability of promoting a node to level \(k\) is \( \frac{1}{2^k} \)

The number of levels is \(O(log \;n)\), therefore, the search time and the time complexity of other operations is \(O(log \; n)\) too. The statement is intuitively correct but requires a proof. A simple proof can be found in Skip Lists - CMSC 420. The idea is to consider the reverse of the path that finds the target element.

Another note is that the nodes are sorted and the multi-level linked list is much like a binary search tree.

----- END -----

©2019 - 2022 all rights reserved