1. Suppose that we create a binary tree by inserting a set of n different keys in a random order, without rebalancing the tree, and with all permutations of the keys being equally likely to be the insertion order. Given two keys x and y in the set, what is the probability that x becomes a child of y? Write your answer as a formula in terms of the distance from x to y in the sorted sequence of all of the keys.


2. Suppose we are given a set of n numbers x1, x2, x3, ... xn. Show that the amortized time for a splay tree to search for the number xi in this set is O(log i).

Hint: it almost works to assign the number xi the weight wi=1/i. However, the sum W of all the weights in this case is proportional to log n, so plugging in these weights to the formula O(log(W/wi)) for the amortized time of a splay tree would give amortized time O(log(log n / (1/i)) = O(log log n + log i) per operation, not good enough when i is small. One way to solve the problem is to find a different set of weights with a smaller total sum.


3. Suppose that we are designing a B+-tree (http://en.wikipedia.org/wiki/B%2B_tree) to hold a set of n keys. What is the smallest block size b that we could choose in order to guarantee that the tree has at most two levels of nodes?