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

|cite|improve this question
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.