Dynamic trees in practice

Robert E. Tarjan, Renato F. Werneck

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

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, lineartime 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.

Original languageEnglish (US)
Article number4.5
JournalACM Journal of Experimental Algorithmics
Volume14
DOIs
StatePublished - Feb 1 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science

Keywords

  • Dynamic trees
  • Experimental evaluation
  • Link-cut trees
  • Top trees

Fingerprint

Dive into the research topics of 'Dynamic trees in practice'. Together they form a unique fingerprint.

Cite this