R-3.12 If one has a set, S, of n items, where n is even, then the median item in S is the

average of the i th and (i+1)st smallest elements in S, where i = n/2. Describe

an efficient algorithm for computing the median of such a set S that is stored in

a binary search tree, T, where each node, v, in T is augmented with a count, nv,

which stores the number of items stored in the subtree of T rooted at v.

R-3.12 Hint: Just describe how to do a search for those two items.