Search⌘ K
Home
Courses
Data Structures with Generic Types in C++

Discussion on Scapegoat Trees

Explore how Scapegoat Trees maintain balance and analyze their efficiency compared to other data structures. Learn about their unique rebuilding mechanisms, performance trade-offs, and scenarios where they provide advantages, especially when nodes hold additional data requiring partial rebuilding for updates.

We'll cover the following...

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

...