Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Dynamic trees in practice

Robert E. Tarjan and Renato F. Werneck

Abstract

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.

Details

Publication typeArticle
Published inACM Journal of Experimental Algorithmics
URLhttp://doi.acm.org/10.1145/1498698.1594231
Pages4.5:1-4.5:21
Volume14
Number4
PublisherAssociation for Computing Machinery, Inc.

Previous versions

Robert E. Tarjan and Renato F. Werneck. Dynamic Trees in Practice, Springer, June 2007.

> Publications > Dynamic trees in practice