Consider an ordinary binary search tree. At each pointer, we keep size (p) which is the number of vertices in the tree rooted by p. We say that p is balanced

if size (left(p))size(p),size(right(p))size(p).

An tree is an balanced tree if every vertex in the tree roots an alpha balanced tree.

(a) Given a vertex p in an arbitrary binary search tree, show how to make the tree 1 / 2-balanced in time O(size(p)).

(b) Show that an -balanced tree has height O(log n )

(c) From now on we speak on > 1/ 2. We apply the following strategy. If when inserting a vertex to the tree, some vertex roots a non

- balanced tree, we apply the procedure to get a 1 / 2-balanced tree. Remark: we do not study deleting vertices albeit its the same.

Let the potential function of p be Q ( p) = | size ( left ( p )) size ( right ( p )) |. and let Q = p Q ( p ) be the potential function with the sum going over all vertices.

Show that the amortize cost of making a tree 1 / 2-balanced is O (1)

(d) Show that Insert into an - balanced tree have amortize cost O (log n )