The term scapegoat tree is due to Galperin and Rivest [33], who define and analyze these trees. However, the same structure was discovered earlier by Andersson [5,7], 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.3 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
[20].

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

- Design, analyze, and implement a modified version of
`ScapegoatTree`where the length of the search path does not exceed , where is a parameter with . - What does your analysis and/or experiments say about the amortized cost of , and as a function of and ?

Your analysis should show that operations on a `CountdownTree` run
in
amortized time. (Hint: First show that each node
satisfies some version of a balance invariant.)

Your analysis should show that operations on a `DynamiteTree` run
in
expected time.

- : Add a new element after the element in the sequence. Return the newly added element. (If is null, the new element is added at the beginning of the sequence.)
- : Remove from the sequence.
- : return if and only if comes before in the sequence.

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
.