Dynamic tree data structures maintain forests that change over time through edge insertions and deletions. Besides maintaining
connectivity information in logarithmic time, they can support aggregation of information over paths, trees, or both. We perform
an experimental comparison of several versions of dynamic trees: ST-trees, ET-trees, RC-trees, and two variants of top trees
(self-adjusting and worst-case). We quantify their strengths and weaknesses through tests with various workloads, most stemming
from practical applications. We observe that a simple, linear-time implementation is remarkably fast for graphs of small diameter,
and that worst-case and randomized data structures are best when queries are very frequent. The best overall performance,
however, is achieved by self-adjusting ST-trees.
Part of this work was done while the second author was at Princeton University. Research partially supported by the Aladdin
Project, NSF Grant 112-0188-1234-12.