Analysis of Skiplists
Discover the advantage of using the skiplists.
We'll cover the following...
Here, we analyze the expected height, size, and length of the search path in a skiplist. This section requires a background in basic probability. Several proofs are based on the following basic observation about coin tosses.
Lemma 1: Let be the number of times a fair coin is tossed up to and including the first time the coin comes up heads. Then,
Proof: Suppose we stop tossing the coin the first time it comes up heads. Define the indicator variable
Note that if and only if the first coin tosses are tails, so Observe that , the total number of coin tosses, can be written as Therefore,
...