+1 vote
in Data Structures & Algorithms I by (110k points)
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.

1 Answer

+1 vote
by (408k points)
selected by
 
Best answer
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).

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.

Categories

...