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
...
Create a free account to access the full course.
By signing up, you agree to Educative's Terms of Service and Privacy Policy