Randomization: Skip Lists

Search(x) in case for level 2

1. walk right in top linked list
2. walk down to bottom linked list
3. walk right if it is last row linked list

In general case Search will take O(logn)

 

Insert(x)

do Search(x) to see where x fits into the bottom list

always insert into last bottom list

decide how much we are going to promote x into upper list.   = we do it with fliping coin , until we get tail we keep promote x to upper list.

 

Delete(x) = you Search(x) and delete all level

 

there are 80% probability that it will be in 2logn , and there is 99.999% probability that it will be in 4logn and so on..

With High Probability == The more we try, the closer we get to a given O(logn) time.

1/2 since we are throwing fair coin.

Total number of moves = nubmer of coin flips until you get c * logn heads (number of up moves)

Claim : Number of coin flip until c * logn heads = O(logn) with high probability