Design of data structures for mergeable trees

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(log² 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: Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 2: Pankaj K. Agarwal , Herbert Edelsbrunner , John Harer , Yusu Wang, Extreme elevation on a 2-manifold, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997871]
• 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: Stephen Alstrup , Mikkel Thorup, Optimal pointer algorithm for finding nearest common ancestors in dynamic trees, Journal of Algorithms, v.35 n.2, p.169-188, May 2000 [doi>10.1006/jagm.2000.1079]
• 5: S. W. Bent, D. D. Sleator, and R. E. Tarjan. Biased search trees. SIAM Journal of Computing, 14(3):545--568, 1985.
• 6: Gerth Stølting Brodal , George Lagogiannis , Christos Makris , Athanasios Tsakalidis , Kostas Tsichlas, Optimal finger search trees in the pointer machine, Journal of Computer and System Sciences, v.67 n.2, p.381-418, September 2003 [doi>10.1016/S0022-0000(03)00013-8]
• 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: Richard Cole, On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof, SIAM Journal on Computing, v.30 n.1, p.44-85, 2000 [doi>10.1137/S009753979732699X]
• 9: Richard Cole , Bud Mishra , Jeanette Schmidt , Alan Siegel, On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences, SIAM Journal on Computing, v.30 n.1, p.1-43, 2000 [doi>10.1137/S0097539797326988]
• 10: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 11: Paul F. Dietz , Rajeev Raman, A constant update time finger search tree, Information Processing Letters, v.52 n.3, p.147-154, Nov. 11, 1994 [doi>10.1016/0020-0190(94)00115-4]
• 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 , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 14: Harold N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 22-24, 1990, San Francisco, California, United States
• 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: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 17: Haim Kaplan , Nira Shafrir , Robert E. Tarjan, Meldable heaps and boolean union-find, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509990]
• 18: K. Mehlhorn , S. Näher, Bounded ordered dictionaries in O(loglogN) time and O(n) space, Information Processing Letters, v.35 n.4, p.183-189, Aug. 1990 [doi>10.1016/0020-0190(90)90022-P]
• 19: Mihai Pǎtraşcu , Erik D. Demaine, Lower bounds for dynamic connectivity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007435]
• 20: Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
• 21: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 22: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 23: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 24: R. E. Tarjan. Amortized computational complexity. SIAM J. Alg. Disc. Meth., 6(2):306--318, 1985.
• 25: Robert E. Tarjan , Renato F. Werneck, Self-adjusting top trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 26: Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]
• 27: Mikkel Thorup, On RAM Priority Queues, SIAM Journal on Computing, v.30 n.1, p.86-109, 2000 [doi>10.1137/S0097539795288246]
• 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: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Theory