A linear time algorithm for the lowest common ancestors problem
- 1 October 1980
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 308-319
- https://doi.org/10.1109/sfcs.1980.6
Abstract
We investigate two lowest common ancestor (LCA) problems on trees. We give a linear time algorithm for the off-line problem, on a random access machine (RAM). The half-line problem is one in which LCA queries on a fixed tree are arriving on line. We extend our RAM algorithm to answer each individual query in 0(1) time, with 0(n) preprocessing time. Tarjan observed that this result helps to explicate the difference in power between RAM and pointer machines. We also show how to modify our algorithm to achieve a linear preprocessing time, optimal query time, algorithm on a reference machine.Keywords
This publication has 9 references indexed in Scilit:
- Storing a sparse tableCommunications of the ACM, 1979
- An Efficient Method for Storing Ancestor Information in TreesSIAM Journal on Computing, 1979
- A dichromatic framework for balanced treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- A new representation for linear listsPublished by Association for Computing Machinery (ACM) ,1977
- Reference machines require non-linear time to maintain disjoint setsPublished by Association for Computing Machinery (ACM) ,1977
- On Finding Lowest Common Ancestors in TreesSIAM Journal on Computing, 1976
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Binary search trees of bounded balancePublished by Association for Computing Machinery (ACM) ,1972
- Symbol manipulation by threaded listsCommunications of the ACM, 1960