The term scapegoat tree is due to Galperin and Rivest [28], who define and analyze these trees. However, the same structure was discovered earlier by Andersson [3,5], who called them general balanced trees since they can have any shape as long as their height is small.
Experimenting with the ScapegoatTree implementation will reveal that it is often considerably slower than the other SSet implementations in this book. This may be somewhat surprising, since height bound of
This gap in performance is due to the fact that, unlike the other SSet implementations discussed in this book, a ScapegoatTree can spend a lot of time restructuring itself. Exercise 8.1 asks you to prove that there are sequences of operations in which a ScapegoatTree will spend on the order of time in calls to . This is in contrast to other SSet implementations discussed in this book that only make structural changes during a sequence of operations. This is, unfortunately, a necessary consequence of the fact that a ScapegoatTree does all its restructuring by calls to [15].
Despite their lack of performance, there are applications in which a ScapegoatTree could be the right choice. This would occur any time there is additional data associated with nodes that cannot be updated in constant time when a rotation is performed, but that can be updated during a operation. In such cases, the ScapegoatTree and related structures based on partial rebuilding may work. An example of such an application is outlined in Exercise 8.5.
What does your analysis and/or experiments say about the amortized cost of , and as a function of ?
Your analysis should show that operations on a WeightBalancedTree run in amortized time.
Your analysis should show that operations on a countdown tree run in amortized time. (Hint: First show that each node satisfies some version of a balance invariant.)
The Sequence data structure can be implemented by storing the elements in something like a ScapegoatTree, in the same order that they occur in the sequence. To implement in constant time, each element is labelled with an integer that encodes the path from the root to . In this way, can be implemented just by comparing the labels of and .