Modelling Dynamic Trees

There exist many algorithms that work over tree graphs. Any of them can use di erent data structures to represent the same tree. If we need to run several of these algorithms over one forest together each one could use its own representation of the forest. Moreover if the forest dynamically changes over the time by edge insertions and deletions all these changes have to be reflected into data structures of all algorithms. This is not efficient. Thus several data structures have been proposed to solve this problem. Any of them is good at some properties, but each has a weak point. It appears that Top Trees provide the most acceptable trade-o ff. This thesis deals with Top Trees. First we build an implementation of the structure and describe it in detail. Then a programming language called Top Tree Friendly Language (TFL) is developed exclusively for algorithm designing over our data structure. It combines declarative and procedural approaches that results in simpler and faster algorithm designing. Finally we present Top Tree Query Language (TQL) that provides an easy Top Trees administration. The implementation of Top Trees, the programming language TFL and the query language TQL together form a complex solution for using Top Trees