Design a perfect SkipList L for a set - {xo,T1...xn-1} of n keys, if only 2 leve

Question

Design a perfect SkipList L for a set - {xo,T1...xn-1} of n keys, if only 2 levels are allowed. What the the time for a query in the worst case. Further explanation. Assume after the SkipList is constructed, and adversary will perform find(x), where the adversary picks what is z. You goal is to decide how to build the SL, so the time for this operation is as small as possible, What would be the structure of the SL, if three levels are allowed Hint: Assume that there is some value , such that the keys that participates in level 2 are xo,ZA, T2,x3A pick to obtain optimal search time? For example, if -10, then the second level contains T0,T10:T20,T30 That is, the gaps between these keys is fixed. How would you

Explanation / Answer

worst case for 2 layers : O(n1/2). If we have n nodes on 2nd layer, we'll have n^1/2 nodes on the first layer, then there will be n^1/2 segments. n^1/2 is actually optimal division with two layers. With this arrangement, the number of nodes traversed for a search will be O(n1/2).

-------------------------

Algorithm for find(x):

1. Key of next node is less than search key then we keep on moving forward on the same level.

2. Key of next node is greater than the key to be inserted then we store the pointer of current node and move one level down and continue our search.

Time complexity : O(log n)

-----------------------

The value of delta would be picked in such a way that n items can be divided with n^1/3 segments.

----------------------

Thank you.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.