# Discussion on Scapegoat Trees

Learn about the origin of scapegoat trees.

## We'll cover the following

## Additional notes

The term scapegoat tree is due to

Experimenting with the `ScapegoatTree`

implementation will reveal that it is often considerably slower than the other `SSet`

implementations in this course. This may be somewhat surprising since the height bound of

$\text{log}_{3/2} q \approx 1.709\log n + O(1)$

is better than the expected length of a search path in a `Skiplist`

and not
too far from that of a `Treap`

. The implementation could be optimized by
storing the sizes of subtrees explicitly at each node or by reusing already
computed subtree sizes. Even with these optimizations, there will always be sequences of `add(x)`

and `delete(x)`

operations for which a `ScapegoatTree`

takes longer than other `SSet`

implementations.

This gap in performance is due to the fact that, unlike the other `SSet`

implementations discussed in this course, a `ScapegoatTree`

can spend a lot
of time restructuring itself. There are
sequences of `n`

operations in which a `ScapegoatTree`

will spend on the order of $n\log n$ time in calls to `rebuild(u)`

. This is in contrast to other `SSet`

implementations discussed in this book, which only make $O(n)$ structural changes during a sequence of `n`

operations. This is, unfortunately, a necessary consequence of the fact that a `ScapegoatTree`

does all its `rebuild(u)`

.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy