Exercise: Scapegoat Trees
Explore how to modify the add(x) method in Scapegoat Trees to prevent unnecessary recomputations of subtree sizes, enhancing the efficiency and balance maintenance of the tree. This lesson guides you through applying these optimizations and prepares you to implement improved tree operations effectively.
We'll cover the following...
We'll cover the following...
Task
Modify the add(x) method for ScapegoatTree so that it does not waste any time recomputing the sizes of subtrees that have already been computed. This is possible because, by ...