CS 261, Spring 2013, Homework 5, Due Thursday, May 16

1. In a binary search tree formed by inserting n > 2 different values in
a random permutation without rebalancing, what is the probability that
the node for the median value has exactly one child node? (Hint: this
event depends only on the relative order of insertion of the median
value and its two closest neighbors in the sorted sequence of inputs.)

   1/3. It has exactly one child when one of its two closest neighbors
   is inserted earlier than it and one later than it. That is, among
   these three values, it should be the one inserted in the middle
   position; each is equally likely to be in the middle, so the
   probability is 1/3.


2. Give pseudocode for an algorithm range(T,l,r) that answers queries
where the inputs to the query are the root node T of a binary search
tree and two numbers l and r, and the output is a collection of all the
keys x_i in T with l < x_i < r. Your algorithm should take time O(h+k)
where h is the height of the tree and k is the length of its output.

   def range(T,l,r):
       if T.key < l:
           range(T.right,l,r)
       else if T.key > r:
           range(T.left,l,r)
       else:
           range(T.left(l,r)
           output T.key
           range(T.right(l,r)

    (The pseudocode can also be written to avoid coding the left and
    right recursive calls twice each, but the simplest way to do that
    makes extra and unnecessary comparisons.)        


3. Suppose that T is a splay tree, on three items with keys 1, 2, and 3,
and that all three of the keys have already been searched for since the
most recent time the set of keys in T changed. Based on this
information, how many different shapes might T possibly have? Draw them
all.

   Three. There are five different shapes of trees that could exist on
   the three keys:
   
   a. 1       b. 1     c.   2     d.   3   e.     3
       \          \        / \        /          /
        2          2      1   3      1          2
         \        /                   \        /
          3      3                     2      1

   However, once key 2 is searched for, the tree will be in shape c, and
   at each step after that it will be in one of the three shapes a, c,
   and e. It is not difficult to verify that every splay operation from
   one of these three shapes returns to this set of three shapes. Therefore,
   a correct answer to this question would draw only the shapes of a, c, and e.