SkipList

Question 1

describe the insert method of the skiplist in pseudo code

Answer 1

p= skipsearch(k)
q = insertafterabove(p, null, (k,v))
e = q.element()

Question 2

describe in words the insertion of a skiplist

Answer 2

insert(x,o)

1. using a randomized algorithm
2. repeatedly toss a coin until we get a tail, using I to denote the number of time heads was obtained
3. if I >= h, add on to the skiplists until h = i+1
4. search for the key x and keep track of the position containing largest key less than x in each list going up till Si
5. for j = 0,1,2,3, …,i insert (x,o) into S till Sj after pj

Question 3

describe in words the removal method

Answer 3

to remove an entry x

1. search for x in the list an find positions p1, …, pj
2. Where position pj is in the list
3. remove p0, …, pi in list S0, …, Si
4. remove all list but one containing the 2 special keys

Question 4

describe the quad node

Answer 4

type of node storing:
element, above, below, prev and next

used to implement a skip list

Question 5

What is the probability of getting i consecutive heads when flipping a coin?

Answer 5

1/2^i

Question 6

Probable size of a skiplist?

Answer 6

n/2^i

Question 7

expected space usage for a skiplist?

Answer 7

O(n)

Question 8

What is the height of a skiplist?

Answer 8

O(log n)

Question 9

search, insertion, and deletion runtime?

Answer 9

O(log n)