×

zbMATH — the first resource for mathematics

Computing on a free tree via complexity-preserving mappings. (English) Zbl 0636.68092
The relationship between linear lists and free trees is studied. We examine a number of well-known data structures for computing functions on linear lists and show that they can be canonically transformed into data structures for computing the same functions defined over free trees. This is used to establish new upper bounds on the complexity of several query- answering problems.

MSC:
68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
68P20 Information storage and retrieval of data
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. · Zbl 0326.68005
[2] J. L. Bentley, Multidimensional divide and conquer,Comm. ACM,23 (1980), 214–229. · Zbl 0434.68049 · doi:10.1145/358841.358850
[3] B. Chazelle, A functional approach to data structures and its use in multidimensional searching,SIAM J. Comput. (in press). Preliminary version inProceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, pp. 165–174.
[4] B. Chazelle and L. J. Guibas, Fractional cascading: I. A data structuring technique,Algorithmica,1 (1986), 133–162. · Zbl 0639.68056 · doi:10.1007/BF01840440
[5] H. Edelsbrunner, A new approach to rectangle intersections, Part II,Internat. J. Comput. Math.,13 (1983) 221–229. · Zbl 0513.68059 · doi:10.1080/00207168308803365
[6] H. N. Gabow, J. L. Bentley, and R. E. Tarjan, Scaling and related techniques for geometry problems,Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 1984, pp. 135–143.
[7] D. Harel and R. E. Tarjan, Fast algorithms for finding nearest common ancestors,SIAM J. Comput.,13 (1984), 338–355. · Zbl 0535.68022 · doi:10.1137/0213024
[8] D. E. Knuth,The Art of Computer Programming, Vol. I, 2nd edn., Addison-Wesley, Reading, MA, 1973 · Zbl 0191.17903
[9] J. Komlós, Linear verification for spanning trees,Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, 1984, pp. 201–206.
[10] E. M. McCreight, Efficient algorithms for enumerating intersecting intervals and rectangles, Technical Report CSL-80-9, Xerox Pare, 1980.
[11] E. M. McCreight, Priority search trees,SIAM J. Comput.,14 (1985), 256–276. · Zbl 0564.68050 · doi:10.1137/0214021
[12] D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees,J. Comput. System Sci.,26 (1983), 362–391. · Zbl 0509.68058 · doi:10.1016/0022-0000(83)90006-5
[13] D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees,J. Assoc. Comput. Mach.,32 (1985), 652–686. · Zbl 0631.68060
[14] R. E. Tarjan, Efficiency of a good but not linear set union algorithm,J. Assoc. Comput. Mach.,22 (1975), 215–225. · Zbl 0307.68029
[15] R. E. Tarjan, Applications of path compression on balanced trees,J. Assoc. Comput. Mach.,26 (1979), 690–715. · Zbl 0413.68063
[16] J. Vuillemin, A unifying look at data structuŕes,Comm. ACM,23 (1980), 229–239. · Zbl 0434.68047 · doi:10.1145/358841.358852
[17] D. E. Willard, New data structures for orthogonal range queries,SIAM J. Comput.,14 (1985), 232–253. · Zbl 0564.68071 · doi:10.1137/0214019
[18] A. C. Yao, Space-time tradeoff for answering range queries,Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982, pp. 128–136.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.