Top Trees: A Generic Data Structure for Tree Augmentations

This paper was written for CS166: Data Structures at Stanford University. Top Trees are a very cool and flexible data structure that can be used to solve a variety of dynamic forest problems very quickly (asymptotically at least) with a simple interface. However, the papers/thesis on this data structure are all over 100 pages long and are very dense. This paper is an attempt to distill the essence of the data structure and the runtime into a more pedegocially digestible form. Additionally, the paper concludes with a potential extension to directed acyclic graphs (DAGs) which is not covered in the original papers.