Task 3. Skip list. Peter Zmeda wants to test his knowledge of skip lists. First, he obtained a sequence of random bits (every fifth value is highlighted for easier orientation): 11010 11011 01000 11101 11000 11111 11111 01000 00 . (1) In addition, he found a sequence of random integers: 46 55 37 95 80 70 15 47 37 86, from which, if we sort it, we get the sequence: (2) 15 37 37 46 47 55 70 80 86 95. (3)
1. (i.) Insert the sequence of numbers from (2) into a binary search tree and draw
the final tree. (ii.) Insert also the sequence of numbers from (3) into a binary
search tree and draw the final tree.
2.(i.) Insert the sequence of numbers from (2) into a skip list, where you should
use the random bits from (1) and draw the final list. (ii.) Insert also the sequence
of numbers from (3) into a skip list, where you should again use the random bits
from (1) and draw the final list.
3.For both trees and for both lists, find the key to which we need the most steps.
(i) For each of the structures, write down that key and how many steps there are
necessary to achieve it.
A perfect skip list has 1 element of height lg n, 2 of height lg n − 1, ..., 2^i
elements of height lg n − i and so on. (ii.) How many elements are of height 1?
Justify your answer. (iii.) How many references (pointers) does a perfect skip list
have? Justify your answer. Comment it in terms of a binary search tree.
Step by step
Solved in 2 steps
