Quick links

Design and Analysis of Data Structures for Dynamic Trees

Report ID:
April 2006
Download Formats:


The dynamic trees problem is that of maintaining a forest that changes
over time through edge insertions and deletions. We can associate data
with vertices or edges and manipulate this data, individually or in
bulk, with operations that deal with whole paths or trees. Efficient
solutions to this problem have numerous applications, particularly in
algorithms for network flows and dynamic graphs in general. Several
data structures capable of logarithmic-time dynamic tree operations
have been proposed. The first was Sleator and Tarjan's ST-tree, which
represents a partition of the tree into paths. Although reasonably
fast in practice, adapting ST-trees to different applications is
nontrivial. Frederickson's topology trees, Alstrup et al.'s top trees,
and Acar et al.'s RC-trees are based on tree contractions: they
progressively combine vertices or edges to obtain a hierarchical
representation of the tree. This approach is more flexible in theory,
but all known implementations assume the trees have bounded degree;
arbitrary trees are supported only after ternarization. This thesis
shows how these two approaches can be combined (with very little
overhead) to produce a data structure that is at least as generic as
any other, very easy to adapt, and as practical as ST-trees. It can be
seen as a self-adjusting implementation of top trees and provides a
logarithmic bound per operation in the amortized sense. We also
discuss a pure contraction-based implementation of top trees, which is
more involved but guarantees a logarithmic bound in the worst case.
Finally, an experimental evaluation of these two data structures,
including a comparison with previous methods, is presented.

Follow us: Facebook Twitter Linkedin