Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Solution: Scapegoat Trees

Explore how to enhance the add method in Scapegoat Trees by reusing previously computed subtree sizes, improving insertion efficiency and maintaining tree balance through targeted rebuilding techniques.

We'll cover the following...

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 ...