4
$\begingroup$

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

$\endgroup$

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.