MSc Thesis Defense by Tyler Huffman


A Survey of Dynamic Tree Data Structures and an Implementation of an Amortized Top Tree


In the field of dynamic connectivity, this thesis aims to provide an implementation of
an amortized top tree using two other fully dynamic data structures; Sleator-Tarjan trees, and topology trees. In addition, this thesis provides a new configuration of a topology tree, using the height and running time bounds described in Sleator-Tarjan trees.

Supervisor: Christian Wulff-Nilsen

Co-supervisor: Eva Rotenberg 

Censor: Rasmus Pagh, professor, ITU