Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$.

We construct a skip list over the keys.

Now if I pick a key (e.g. 31 in the following picture), what are the Expected value of keys that it points to?

For example, key 31 points to: [38,44,55]. Considering that I know 31 has k pointers (here k=3), how can I compute the expected distribution of values it points to?

P.S. I am also interested to compute the INDEX of values it points to (e.g. 31 is the 5th key, and points to 6th, 8th, and 10th keys). Can I infer these [expected] index numbers, too?

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.