In Java

Analyze and implement a CountdownTree. In a Countdown- Tree each node u keeps a timer u.t. The add(x) and remove(x) opera- tions are exactly the same as in a standard BinarySearchTree except that, whenever one of these operations affects us subtree, u.t is decremented. When u.t = 0 the entire subtree rooted at u is rebuilt into a perfectly balanced binary search tree. When a node u is involved in a rebuilding operation (either because u is rebuilt or one of us ancestors is rebuilt) u.t is reset to size(u)/3.

Your analysis should show that operations on a CountdownTree run in O(log n) amortized time. (Hint: First show that each node u satisfies some version of a balance invariant.)