1. Prove that the amortized cost of a top-down splay is O(log N).
2. Prove that there exist access sequences that require 2 log N rotations per access for bottom-up splaying. Show that a similar result holds for top-down splaying.
3. Modify the splay tree to support queries for the kth smallest item.
4. Compare, empirically, the simpli?ed top-down splay with the originally described top-down splay.
5. Write the deletion procedure for red-black trees.