Question

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

Asked question is from Skip List in chapter Types of Lists of Data Structures & Algorithms I

The question was asked in semester exam.

Answer 1

The correct answer is (a) design each level of a multi-level skip list with varied probabilities

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