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 the height bound of
...