4. Skiplists

In this chapter, we discuss a beautiful data structure: the skiplist, which has a variety of applications. Using a skiplist we can implement a $\mathtt{List}$ that has $O(\log n)$ time implementations of $\mathtt{get(i)}$, $\mathtt{set(i,x)}$, $\mathtt{add(i,x)}$, and $\mathtt{remove(i)}$. We can also implement an $\mathtt{SSet}$ in which all operations run in $O(\log \ensuremath{\mathtt{n}})$ expected time.

The efficiency of skiplists relies on their use of randomization. When a new element is added to a skiplist, the skiplist uses random coin tosses to determine the height of the new element. The performance of skiplists is expressed in terms of expected running times and path lengths. This expectation is taken over the random coin tosses used by the skiplist. In the implementation, the random coin tosses used by a skiplist are simulated using a pseudo-random number (or bit) generator.