Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Discussion on Scapegoat Trees

Learn about scapegoat trees, including their history, structural properties, and performance implications. This lesson helps you understand why scapegoat trees may be slower than other set implementations and when their unique rebuilding operations are beneficial in managing additional node data.

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

...