![[topimage]](IMADA_en.png)
Exercises
- Sometimes we are interested in having a next operation which, given a reference to an element, returns a reference to the element with the next higher key. How could this be implemented in a tree structure such as red-black trees, for example. How would it be done for skip lists? What about hash tables? What about previous, i.e., finding the largest key smaller than the current one?
- Consider the details around maintaining maxLevel for skip lists, i.e., when and how to change it, and how to make sure that the complexity bounds (which are based on L(n)) still hold.
- For skip lists, we consider the implementation of meld - the union of two sets of keys where all keys in one set is smaller than all keys in the other, and the implementation of split - splitting the set of keys in two depending given af key as argument. How should maxLevel be adjusted to be close to L(n)? Importantly, in order to compute L(n), we need to know n. How can you add information to the skip list structure and maintain this such that n can always be determined in expected time O(1)? Could we do something reasonable without n?
- Prove that one gets the best constant for the expected search time by choosing p=1/e as claimed in Table 1 of [P89]. Then explain all the other constants in the table. You need to manipulate the logarithmic expressions some to reverse engineer the table data.
- Consider a standard binary heap. Is it possible to make an O(n) traversal of the heap and print all the priorities in non-decreasing order during that traversal? Argue your position.