CS410, Summer 1998
Homework 3 Sample Solution
Dan Grossman

Questions 1,2,3,4,6,7 worth 15 points each.
Question 5 worth 10 points.

1.	1 *     ======> 1 *     ======>       2 *     =====>        2 *
                case 0     \    case 4        /  \    cases 1,0    /  \
                          2 O               1 O  3 O	         1 *  3 *
			                                                 \
							                4 O
=====>      2 *	     ======>   2 *     =====>    2 * 
case 4    /   \      case 0   /   \   case 3     /  \
         1 *  4 *           1 *  5 *          1 *  4 *
              /   \               /                /   \
            3 O  5 O            3 O             3 O   5 O

======>   2 *         ======>   2 *      =====>      2 *  ====>  2 * 
case 0    /  \        case 0    /  \    cases 3,1    /   case 0
       1 *  4 *               1 * 5 *              1 O
               \
              5 O

2.	1      =====>    o    =====>     o   ====>    o     =====>      o
                        / \             /|\         /   \            /    \
                       1   2           1 2 3       o     o          o      o
                                                  / \   / \        / \   / | \
                                                 1  2  3   4      1   2 3  4  5

====>     o	   ====>   o        ======>  o       =====>    o    ===> o
        /    \           /   \             /   \             / | \      / \
       o      o         o      o          o     o           1  2  5    1   2
      / \   /   \     /  \   / | \      /   \  /  \
     1   2 3    5    1   2  3  4  5    1    2 4    5

====>  2


3. Claim: If the difference between the longest and the shortest
root-to-leaf path in a binary tree is a constant factor, then the
length of the longest path is O(log n) where n is the number of nodes.

Proof: Let h be the length of the longest path, s the length of the
shortest.  Then for a constant k, we know h <= sk.  Since s is the
length of the shortest path, the first s levels of the tree must be
complete.  That is, the tree must have 2^(s+1) - 1 > 2^s nodes in it!  So,
	n > 2^s 
taking log of both sides:
        log n > s
and we know 
	s >= h/k
so,
	log n > h/k
i.e.
	klog n > h
so,
	h is O(log n)

4. Claim: Any n-node binary tree can be transformed into any other
n-node binary tree by a sequence of O(n) rotations.

Proof:  
First we prove some other helper claims:
  1. Claim: If A can be transformed into B by m rotations, then B can be 
     transformed into A by m rotations.
  Proof: This is "obvious" since left rotation and right rotation are inverse
	 operations.  To be totally technical, you should prove they are
	 inverses and then conclude by a trivial proof by induction that
	 a series of m rotations has an inverse series of m rotations.

  2. Claim: Any tree A can be transformed into a tree with no left children
     in O(n) rotations.
  Proof:  Let r be the path starting at the root and following right pointers.
	  Initially in A, the height of r is >= 0.  If the height is n-1, then
	  we are done.  Therefore, it suffices to show that we can make the
	  height of r be at least i after i rotations (for i <= n-1). 
	   We prove this by  induction on i.
	(base) i=0
		After no work the height of r is >=0. 
	(ind) 0 < i < (n-1)  
		Since the height is < (n-1), some node x on r has a left child.
		Rotate x to the right.  By inspection, this adds 1 to the
	        height of r and results in a tree A'.  By the inductive 
		hypothesis, we can perform i-1 rotations on A' and further
		increase the height of r by (i-1).  (Or else, the height is
		n-1 and we're done).  So in i rotations, we increase the height
		by i.

5. Simply use 2 dictionaries instead of 1. 

For example, keep two balanced trees behind the scenes, each indexed
by one of the relevant keys.  On insert, put the object in both
dictionaries, using the appropriate key.  On deletion, delete the
object from both dictionaries.  (If you're only given one key, delete
the object from one dictionary, but not before getting the value of
the other key from the object you're deleting.) On lookup, use only
the dictionary that is indexed on the key provided.

6. 
 1. On lookup, upon finding one value with the key we would have to follow
    _both_ subtrees looking for more values.  After finding i such values,
    we could potentially be following 2^i paths.  This destroys the O(h)
    bound (where h is the height of the tree).

 2. The height of the tree is now O(max(log n, m)) where m is the frequency
    of the most-frequently-occurring key.  If m > log n, then we have a worse
    bound.

 3. At each node, put a linked list of values that have the same key.

7.
   1. Store at each node the number of _leaves_ in the subtree rooted at the
      node.  Call this x.count.  Then to answer rank(key), we descend the tree
      as we would for lookup, but at each step we add the count value of all
      left siblings to a running total.  This running total is rank(key) once
      we reach the leaf.
 
   2. insert: on the way down, add 1 to the count of every node that is passed.
	      on the way up, as a node is split, set the count of each new
	      node to the sum of the counts of its children.

      delete: on the way down, subtract 1 from the count of every node that
	      is passed.
	      on the way up, if a node x is moved, subtract x.count from x's
	      old parent and add x.count to x's new parent.  (Note: it is not
	      necessary to propagate this information further because the
	      old and new parents share a grandparent.)
   4. numBetween(key1, key2) = rank(key2) - rank(key1) - 1