Solution: Scapegoat Trees

Task

Here is the solution that modifies the add(x) method of the ScapegoatTree so that it does not waste any time recomputing the sizes of subtrees that have already been computed. This is possible because, by the time the method wants to compute size(w), it has already computed one of size(w.left) or size(w.right).

Solution

We have implemented the code that modifies the add() method of the ScapegoatTree. The add() method inserts a new element x into the ScapegoatTree and rebalances the tree if the depth exceeds a certain threshold.