Problem 4: Consider a binary search tree augmented with the following information. At each node x we also store m(x): the number of nodes in the subtree rooted at x (including x).

Show how to use the field m(x) to answer queries of the form Statistic(T, i) which returns the i th element in sorted order of T, in time O(h) where h is the height of the tree.

Show how to update m(x) when you do insertions and deletions.

So far the tree is not balanced, and insertions and deletions can force it to be unbalanced. Suppose we want to use the m(x) field to keep the tree balanced by enforcing the condition that for every node x in the tree |m(L(x)) m(R(x))| 1.

Prove that h = O(log n) where h is the height of a tree with n nodes satisfying this property

Show however that this condition is too strict and that maintaining will force certain insertion and deletion operations to cost (log n) (build an example where insertion or deletion require many rotations to fix the tree)

What can you do to make sure that h = O(log n) and all operations (including Statistic, Insert and Delete) run in time O(h) = O(log n).

Note:if you need any information ask me please