Top-trees implementation

Title: Top Trees implementation Author: Jifi Sofka Department: Department of Theoretical Computer Science and Mathemat- ical Logic Supervisor: Mgr. Vladan Majerech, Dr. Supervisor's e-mail address: Vladaii.Majerech@mff.cmii.cz Abstract: Dynamic data structure Top Trees is used to represent a tree by a binary structure of tree contractions. Vertices of such a binary tree are called clusters. Each cluster represents one contraction and contains aggregated data of its children. One of the main advantages of Top Trees is the separation of cluster's data management into Create, Destroy, Join, Split and Select functions which are automatically called as the internal structure of Top Trees changes. The implementation of Top Trees is therefore independent of all the properties that are tracked about the original tree (i.e. 2-connecticity, tree median). The size of cluster's aggrefated data about one tree property may de- pend on the size of the entire original tree and its calculation can be time consuming. The operations used to query the Top Tree about different tree properties often result in Top Tree structural changes. In the original Top Tree design, each of the affected clusters needs to update the data belong- ing to all tracked properties when such structural change occurs. Not all of the properties are..