A skip list is a data structure for fast access to an ordered set of data. It can be used as an alternative to a binary search tree, and in fact can be viewed as a (not necessarily binary) tree structure. It is actually a sequence of lists, with the initial list containing all the data in sorted order. Each successive list is defined as a copy of the previous with some elements deleted, so each provides a coarser partition of the data, until the empty list is reached. The heads of the lists are linked together from the shortest to the initial list. Each element that was not deleted is also linked to the same element in the previous list. If the lists are viewed as horizontal, then vertical links connect the heads of the list and all the copies of the same element, with all vertical links going from the shortest list to the longest.

The empty list corresponds to the root of the tree, and the vertical links go to the leftmost child. The horizontal links are used to find the remaining children (if any).

A randomized skip list can be defined by deleting each element independently with probability 1/2. This makes the lengths of the vertical chains geometric random variables, and for a given chain, the probability that its height is at least k is 1/2k. the probability that the height of the tallest chain is at most t is thus bounded by n/2t, so with high probability the height of the skip list is O( lg n ).

The Find operation starts at the root, and at each step it follows one vertical link and zero or more horizontal links until it either finds the element it's looking for or stops just before a larger element. The expected number of horizontal links that Find follows at each level is at most 2, since it stops at the point when an element was deleted in the next level, and each element is deleted with probability 1/2. Thus the expected time for Find is at most twice the expected height, and is also O( lg n ). Note: Calculating the joint expectation of the product of two random variables is like calculating a double sum or a double integral. Just as in these cases, it may not be equal to the product of the individual expectations. Here, we can get a uniform bound of 2 on the inner expectation so the multiplication by 2 is valid, as it would be if the inner sum or integral always evaluated to (or was bounded by) a constant. An Insert can be performed by letting the height be zero with probability 1/2, one with probability 1/4, two with probability 1/8, etc. as for the other elements. If the result is larger than the current height new levels are created. In any case, intervals in previous levels are split in the order they would be encountered in a Find operation. Similarly, Delete involves merging intervals in the order they would be encountered in a Find operation (imagine searching for a nonexistent element adjacent to the one being inserted or deleted). In either case, an argument similar to the one used for Find shows that all three operations take time O(lg n ).

References:

Willam Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, vol 33, no. 6, June 1990, pp. 668-76.

Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995