skip to main content
10.5555/1109557.1109602acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Design of data structures for mergeable trees

Published: 22 January 2006 Publication History

Abstract

Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant allows an operation that merges two tree paths. In contrast to the standard problem, in which only one tree arc at a time changes, a single merge operation can change many arcs. In spite of this, we develop a data structure that supports merges and all other standard tree operations in O(log2 n) amortized time on an n-node forest. For the special case that occurs in the motivating application, in which arbitrary arc deletions are not allowed, we give a data structure with an O(log n) amortized time bound per operation, which is asymptotically optimal. The analysis of both algorithms is not straightforward and requires ideas not previously used in the study of dynamic trees. We explore the design space of algorithms for the problem and also consider lower bounds for it.

References

[1]
U. A. Acar, G. E. Blelloch, R. Harper, J. L. Vittes, and S. L. M. Woo. Dynamizing static algorithms, with applications to dynamic trees and history independence. In Proc. 15th ACM-SIAM Symp. on Discrete Algorithms, pages 524--533, 2004.
[2]
P. K. Agarwal, H. Edelsbrunner, J. Harer, and Y. Wang. Extreme elevation on a 2-manifold. In Proc. 20th Symp. on Comp. Geometry, pages 357--365, 2004.
[3]
S. Alstrup, J. Holm, K. de Lichtenberg, and M. Thorup. Maintaining diameter, center, and median of fully-dynamic trees with top trees. Unpublished manuscript, http://arxiv.org/abs/cs/0310065, 2003.
[4]
S. Alstrup and M. Thorup. Optimal algorithms for finding nearest common ancestors in dynamic trees. Journal of Algorithms, 35:169--188, 2000.
[5]
S. W. Bent, D. D. Sleator, and R. E. Tarjan. Biased search trees. SIAM Journal of Computing, 14(3):545--568, 1985.
[6]
G. S. Brodal, G. Lagogiannis, C. Makris, A. Tsakalidis, and K. Tsichlas. Optimal finger search trees in the pointer machine. Journal of Computer and System Sciences, 67(2):381--418, 2003.
[7]
M. R. Brown and R. E. Tarjan. Design and analysis of a data structure for representing sorted lists. SIAM Journal on Computing, 9(3):594--614, 1980.
[8]
R. Cole. On the dynamic finger conjecture for splay trees. Part II: The proof. SIAM Journal on Computing, 30(1):44--85, 2000.
[9]
R. Cole, B. Mishra, J. Schmidt, and A. Siegel. On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences. SIAM Journal on Computing, 30(1):1--43, 2000.
[10]
P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th ACM Symp. on Theory of Computing, pages 365--372, 1987.
[11]
P. F. Dietz and R. Raman. A constant update time finger search tree. Information Processing Letters, 52(3):147--154, 1994.
[12]
G. N. Frederickson. Data structures for on-line update of minimum spanning trees, with applications. SIAM Journal of Computing, 14:781--798, 1985.
[13]
M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In Proc. 21th ACM Symp. on Theory of Computing, pages 345--354, 1989.
[14]
H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, pages 434--443, 1990.
[15]
L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. 19th Symp. on Foundations of Computer Science, pages 8--21, 1978.
[16]
D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338--355, 1984.
[17]
H. Kaplan, N. Shafrir, and R. E. Tarjan. Meldable heaps and boolean union-find. In Proc. 34th ACM Symp. on Theory of Computing, pages 573--582, 2002.
[18]
K. Mehlhorn and S. Näher. Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters, 35(4):183--189, 1990.
[19]
Mihai Pǎtraşcu and Erik D. Demaine. Lower bounds for dynamic connectivity. In Proc. 36th ACM Symp. on Theory of Computing, pages 546--553, 2004.
[20]
B. Schieber and U. Vishkin. On finding lowest common ancestors: Simplification and parallelization. SIAM Journal on Computing, 17(6):1253--1262, 1988.
[21]
D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26:362--391, 1983.
[22]
D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652--686, 1985.
[23]
R. E. Tarjan. Data Structures and Network Algorithms. SIAM Press, Philadelphia, PA, 1983.
[24]
R. E. Tarjan. Amortized computational complexity. SIAM J. Alg. Disc. Meth., 6(2):306--318, 1985.
[25]
R. E. Tarjan and R. F. Werneck. Self-adjusting top trees. In Proc. 16th ACM-SIAM Symp. on Discrete Algorithms, pages 813--822, 2005.
[26]
R. E. Tarjan and C. J. Van Wyk. An O(n log log n)-time algorithm for triangulating a simple polygon. SIAM Journal on Computing, 17(1):143--173, 1988.
[27]
M. Thorup. On RAM priority queues. SIAM Journal on Computing, 30(1):86--109, 2000.
[28]
A. K. Tsakalides and J. van Leeuwen. An optimal pointer machine algorithm for finding nearest common ancestors. Technical Report RUU-CS-88-17, U. Utrecht Dept. of Computer Science, 1988.
[29]
P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80--82, 1977.
[30]
P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99--127, 1977.
[31]
A. Yao. Should tables be sorted? Journal of the ACM, 28(3):615--628, 1981.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2019)Computing height persistence and homology generators in R3 efficientlyProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310599(2649-2662)Online publication date: 6-Jan-2019
  • (2011)Computing elevation maxima by searching the gauss sphereACM Journal of Experimental Algorithmics10.1145/1963190.197037516(2.1-2.13)Online publication date: 27-Jul-2011
  • (2011)Data structures for mergeable treesACM Transactions on Algorithms10.1145/1921659.19216607:2(1-30)Online publication date: 31-Mar-2011
  • (2010)Mergeable dictionariesProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880938(164-175)Online publication date: 6-Jul-2010
  • (2010)A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexesProceedings of the twenty-sixth annual symposium on Computational geometry10.1145/1810959.1811005(267-276)Online publication date: 13-Jun-2010
  • (2009)Computing Elevation Maxima by Searching the Gauss SphereProceedings of the 8th International Symposium on Experimental Algorithms10.1007/978-3-642-02011-7_26(281-292)Online publication date: 4-Jun-2009

View Options

Login options

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