Motivated by an application in computational geometry, we consider a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees. This variant includes an operation that merges two tree paths. In contrast to the standard problem, in which a single operation can only add or delete one arc, one merge can add and delete up to a linear number of arcs. In spite of this, we develop three different methods that need only polylogarithmic time per operation. The first method extends a solution of Farach and Thorup [1998] for the special case of paths. Each merge takes O (log 2 n ) amortized time on an n -node forest and each standard dynamic tree operation takes O (log n ) time; the latter bound is amortized, worst case, or randomized depending on the underlying data structure. For the special case that occurs in the motivating application, in which arbitrary arc deletions (cuts) do not occur, we give a method that takes O (log n ) time per operation, including merging. This is best possible in a model of computation with an Ω( n log n ) lower bound for sorting n numbers, since such sorting can be done in O ( n ) tree operations. For the even-more-special case in which there are no cuts and no parent queries, we give a method that uses standard dynamic trees as a black box: each mergeable tree operation becomes a constant number of standard dynamic tree operations. This third method can also be used in the motivating application, but only by changing the algorithm in the application. Each of our three methods needs different analytical tools and reveals different properties of dynamic trees.

Loukas Georgiadis

Haim Kaplan

Nira Shafrir

Robert E. Tarjan

Renato F. Werneck

ACM Transactions on Algorithms

ACM TRANSACTIONS ON ALGORITHMS 欢迎提交最高质量的原始研究，处理本质上离散和有限的算法，并且在目标或分析中以自然的方式具有数学内容。最受欢迎的是新算法和数据结构、新的和改进的分析以及复杂性结果。该杂志涵盖的具体计算领域包括组合搜索和对象；计数；离散优化和近似；随机化和量子计算；并行和分布式计算；图形算法、几何、算术、数论、字符串；在线分析；密码学；编码;数据压缩;学习算法;算法分析方法;离散算法应用于生物学、经济学、博弈论、通信、计算机系统与体系结构、硬件设计、科学计算等应用领域

ACM Transactions on Algorithms welcomes submissions of high-quality original research that deals with discrete and finite algorithms, naturally incorporating mathematical content in its objectives or analyses. We particularly encourage new algorithms and data structures, novel and improved analyses, and complexity results. The specific computational areas covered by the journal include combinatorial search and objects, counting, discrete optimization and approximation, randomized and quantum computing, parallel and distributed computing, graph algorithms, geometry, arithmetic, number theory, string processing, online analysis, cryptography, coding, data compression, learning algorithms, algorithmic analysis methods, and the application of discrete algorithms in fields such as biology, economics, game theory, communications, computer systems and architecture, hardware design, and scientific computing.

《ACM Transactions on Algorithms》欢迎提交高质量的原创研究，主要涉及离散和有限算法，且在目标或分析中自然包含数学内容。我们特别欢迎新算法和数据结构的提出、新的和改进的分析方法，以及复杂性结果的研究。该期刊涵盖的具体计算领域包括组合搜索与对象、计数、离散优化与近似、随机化与量子计算、并行与分布式计算、图算法、几何、算术、数论、字符串处理、在线分析、密码学、编码、数据压缩、学习算法、算法分析方法，以及离散算法在生物学、经济学、博弈论、通信、计算机系统与体系结构、硬件设计、科学计算等领域的应用。

Data structures for mergeable trees

This work considers a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees that includes an operation that merges two tree paths, and develops three different methods that need only polylogarithmic time per operation.

Category	Quartile
计算机科学	3
计算机科学, 计算机理论方法	2
计算机科学, 应用数学	2

Data structures for mergeable trees

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
MATHEMATICS, APPLIED	3