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 ).
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995