Search⌘ K
Home
Courses
Data Structures with Generic Types in Java

Discussion on Scapegoat Trees

Explore the concept of Scapegoat Trees and understand their approach to maintaining balance in search trees. This lesson covers their origins, structural characteristics, and how they differ in performance from other balanced trees. You will gain insights into why Scapegoat Trees may be slower due to their restructuring method and identify scenarios where their rebuilding process is advantageous, especially when updating complex 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

log3 ...