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?