Description
You are on your honour to present your own work and acknowledge your sources.
1. [6 marks: Splay Trees] One feature of splaying versus the simple move to root heuristic
is that in performing a splay operation (i.e. performing the appropriate splay operations
to move a node to the root), no node has its depth increased by more than 2. Prove this.
2. [6 marks: splay trees versus static optimal] Give an example of an arbitrarily long
sequence of search requests for n key values such that the cost in a splay tree is “much”
(i.e. more than a constant factor) less than that of the static optimal. Give both costs.