Problem:

In this assignment, you will implement a Countdown Tree, in the file CountdownTree.java. This is a balanced search tree that uses partial rebuilding in a manner similar to scapegoat trees (see OpenDataStructures.org: Scapegoat Trees).

Every countdown tree has a float parameter d, defined when it is created. We call this the tree's countdown delay factor.

Each node u in a countdown tree has an int countdown timer, u.timer. When a new node is created, it's timer is set to Math.ceil(d).

When a node u's timer reaches 0, the node explodes, and the entire subtree rooted at u is rebuilt into a perfectly balanced binary search tree (note that u is probably not the root of this new subtree). Every node v in the rebuilt subtree has it's timer reset to Math.ceil(d*size(v)) where size(v) denotes the number of nodes in the subtree rooted at v.

The add(x) operation in a countdown tree works just like adding in a normal (unbalanced) Binary Search Tree. A new node u containing the value x is added as a leaf in the tree, but in addition u.timer is set to Math.ceil(d). Next, every node on the path from u to the root of the tree has its timer decremented and, if any of these nodes' timers drop to 0, then their subtree 'explodes'.

The remove(x) operation works just like in a normal (unbalanced) Binary Search Tree. We first find the node w that contains x. Now, it might not be easy to remove wbecause it has two children so we try to find a node u that is easy to delete. If w has no right child, then we set u=w. Otherwise, we pick u to be the leftmost (smallest value) node in w's right subtree. Next we swap u.x and w.x and splice u out of the tree.

Finally, we walk back up the path from (the now removed) u to the root and decrement the timer of every node along the way. If any of these nodes' timers drop to 0, then their subtree explodes.

You don't need to do anything to implement the find(x) operation, it's inherited from the BinarySearchTree class and works unmodified.

Use the provided archive to begin your assignment: comp2402a5.zip