skip to main content
research-article

Data structures for mergeable trees

Published: 31 March 2011 Publication History

Abstract

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(log2n) 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.

References

[1]
Acar, U. A., Blelloch, G. E., Harper, R., Vittes, J. L., and Woo, S. L. M. 2004. Dynamizing static algorithms, with applications to dynamic trees and history independence. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 524--533.
[2]
Agarwal, P. K., Edelsbrunner, H., Harer, J., and Wang, Y. 2004. Extreme elevation on a 2-manifold. In Proceedings of the 20th Annual Symposium on Computational Geometry. 357--365.
[3]
Agarwal, P. K., Edelsbrunner, H., Harer, J., and Wang, Y. 2006. Extreme elevation on a 2-manifold. Discr. Comput. Geom. 36, 4, 553--572.
[4]
Alstrup, S., Holm, J., Thorup, M., and de Lichtenberg, K. 2005. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algor. 1, 2, 243--264.
[5]
Bent, S. W., Sleator, D. D., and Tarjan, R. E. 1985. Biased search trees. SIAM J. Comput. 14, 3, 545--568.
[6]
Brown, M. R. and Tarjan, R. E. 1979. A fast merging algorithm. J. ACM 26, 2, 211--226.
[7]
Cole, R. 2000. On the dynamic finger conjecture for splay trees. Part II: The proof. SIAM J. Comput. 30, 1, 44--85.
[8]
Cole, R., Mishra, B., Schmidt, J., and Siegel, A. 2000. On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences. SIAM J. Comput. 30, 1, 1--43.
[9]
Farach, M. and Thorup, M. 1998. String matching in Lempel-Ziv compressed strings. Algorithmica 20, 388--404.
[10]
Frederickson, G. N. 1985. Data structures for on-line update of minimum spanning trees, with applications. SIAM J. Comput. 14, 4, 781--798.
[11]
Frederickson, G. N. 1997. A data structure for dynamically maintaining rooted trees. J. Algor. 24, 1, 37--65.
[12]
Georgiadis, L., Tarjan, R. E., and Werneck, R. F. 2006. Design of data structures for mergeable trees. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 394--403.
[13]
Goldberg, A. V., Grigoriadis, M. D., and Tarjan, R. E. 1991. Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Math. Program. 50, 277--290.
[14]
Kaplan, H. and Shafrir, N. 2008. Path minima in incremental unrooted trees. In Proceedings of the 16th European Symposium on Algorithms (ESA). 565--576.
[15]
Kaplan, H., Shafrir, N., and Tarjan, R. E. 2002. Meldable heaps and boolean union-find. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC). 573--582.
[16]
Pătraşcu, M. and Demaine, E. D. 2006. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35, 4, 932--963.
[17]
Sleator, D. D. and Tarjan, R. E. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3, 362--391.
[18]
Sleator, D. D. and Tarjan, R. E. 1985. Self-Adjusting binary search trees. J. ACM 32, 3, 652--686.
[19]
Smid, M. 1990. A data structure for the union-find problem having good single-operation complexity. Algor. Rev. Newlett. ESPRITT II Basic Res. Actions Program Project no. 3072 (ALCOM) 1.
[20]
Tarjan, R. E. 1975. Efficiency of a good but not linear set union algorithm. J. ACM 22, 2, 212--225.
[21]
Tarjan, R. E. and Werneck, R. F. 2005. Self-Adjusting top trees. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 813--822.
[22]
Tarjan, R. E. and Wyk, C. J. V. 1988. An O(n log log n)-time algorithm for triangulating a simple polygon. SIAM J. Comput. 17, 1, 143--173.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms
ACM Transactions on Algorithms  Volume 7, Issue 2
March 2011
284 pages
ISSN:1549-6325
EISSN:1549-6333
DOI:10.1145/1921659
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 March 2011
Accepted: 01 February 2010
Revised: 01 November 2009
Received: 01 February 2008
Published in TALG Volume 7, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Amortized efficiency
  2. computational topology
  3. critical pairs
  4. dynamic trees
  5. extreme points
  6. link-cut trees
  7. manifolds
  8. merging

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)14
  • Downloads (Last 6 weeks)2
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media