Work Note 7, DM206, fall 2008

Exercises November 19

1. Argue that a ½-weight-balanced Scapegoat tree has minimal height.
2. 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.
3. 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 pros & cons of this.
4. One could also register the potential of a node with that node. What could that be used for?
5. Make a 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 subtree T and count(T) counts the nodes in the subtree T.