Discussion on Scapegoat Trees

Additional notes

The term scapegoat tree is due to Galperin and RivestI. Galperin and R. Rivest. Scapegoat trees. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 165–174. Society for Industrial and Applied Mathematics, 1993., who defined and analyzed these trees. However, the same structure was discovered earlier by AnderssonA. Andersson. Improving partial rebuilding by using simple balance criteria. In F. K. H. A. Dehne, J.-R. Sack, and N. Santoro, editors, Algorithms and Data Structures, Workshop WADS ’89, Ottawa, Canada, August 17–19, 1989, Proceedings, volume 382 of Lecture Notes in Computer Science, pages 393–402. Springer, 1989., who called them general balanced treesA. Andersson. General balanced trees. Journal of Algorithms, 30(1):1–18, 1999. 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 course. This may be somewhat surprising, since 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) operation 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 restructuringP. Dietz and J. Zhang. Lower bounds for monotonic list labeling. In J. R. Gilbert and R. G. Karlsson, editors, SWAT 90, 2nd Scandi- navian Workshop on Algorithm Theory, Bergen, Norway, July 11–14, 1990, Proceedings, volume 447 of Lecture Notes in Computer Science, pages 173–180. Springer, 1990. by calls to rebuild(u).