1. Suppose we wish to maintain a dynamic set S of real numbers (subject to insertion and deletion operations) and, after each insertion or deletion, report the closest pair of numbers in S. Insertions, deletions, and reporting the closest pair should all take time O(log n) or better, where n is the number of elements in S.

(a) Explain how to solve this by augmenting a binary search tree to contain extra information within each node that allows the closest pair to be found quickly after each update. What information do you need to store? How can this information be updated after a rotation in the binary search tree?

(b) Describe a different solution to the same problem that uses an unmodified binary search tree together with a priority queue of adjacent pairs. When you perform an insertion or deletion in the binary search tree, what changes would that cause in the priority queue?


2. Draw a Cartesian tree for the sequence 21 94 17 45 108 121 350 290 6 33 27 104 41.


3. Suppose that, in a given binary tree, we wish to be able to answer queries that take as arguments two nodes x and y and return the first edge on the path from x to y in the tree. Describe how to solve this problem in constant time per query using lowest common ancestors.