[Solved] How to maintain multi-level skip list properties when insertions and deletions are done?

How to maintain multi-level skip list properties when insertions and deletions are done?

a) design each level of a multi-level skip list with varied probabilities
b) that cannot be maintained
c) rebalancing of lists
d) reconstruction

Answer: a
Explanation: For example consider a 2 level skip list. the level-2 skip list can skip one node on an average and at some places may skip 2 nodes, depending on probabilities. this ensures O(logn).

Comments