![[topimage]](IMADA_en.png)
Exercises
- Use illustrations to go through the recursive method for the restructuring of a subtree of a Scapegoat tree which is used in Section 6.1, and make it clear which references must be maintained during the process. You should basically make a correctness proof using drawings.
- In Scapegoat trees, we often need to know the sizes of subtrees. Instead of computing these, we could consider storing these values in the nodes. Consider the advantages and disadvantages of this.
- One could also register the potential of a node with that node. What could that be used for?
-
Make an algorithmic sketch of how the insertion procedure should be coded.
Note that there are no parents pointers. Assume that you have
the following procedures available:
restructure(T)restructures the subtreeTandcount(T)counts the nodes in the subtreeT. - Leftover problems from earlier.