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?

One way to do this would be to store three values in each node x:
- x.small is the smallest key stored at a descendant of x
- x.large is the largest key stored at a descendant of x
- x.pair is the pair of descendants of x with the smallest gap

These can be updated with the following formulas after a rotation involving x:
- x.small = x.left.small
- x.large = x.right.large
- x.pair = min(x.left.pair, x.right.pair, (x.left.large,x.right.small))
where the comparison in the min is done according to the distance of the pair.

Then, the desired information would be stored at the root of the 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?

When inserting x in S:
 - use the binary search tree to find its predecessor y and its successor z in the sorted order
 - remove the pair (y,z) from the priority queue and add the pairs (y,x) and (x,z)

When deleting x from S:
 - again use the binary search tree to find its predecessor y and its successor z in the sorted order
 - add the pair (y,z) to the priority queue and remove the pairs (y,x) and (x,z)

In both cases there would be some additional special cases to handle the situation where x is first or last in the sorted order.

Then, the desired information will be stored as the minimum pair 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.

- This would be tedious with ASCII art so I'll omit it from the solutions


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.

if LCA(x,y) == x:
   if LCA(x.left,y) == x:
      first edge is from x to x.right
   else:
      first edge is from x to x.left
else:
   first edge is from x to x.parent