On Finding Lowest Common Ancestors in Trees
1976; Society for Industrial and Applied Mathematics; Volume: 5; Issue: 1 Linguagem: Inglês
10.1137/0205011
ISSN1095-7111
AutoresAlfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman,
Tópico(s)Error Correcting Code Techniques
ResumoTrees in an n-node forest are merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. We show that any sequence of $O(n)$ such instructions can be processed "on-line" in $O(n\log n)$ steps on a random access computer. If we can accept our answer "off-line", that is, no answers need to be produced until the entire sequence of instructions has been seen, then we may perform the task in $O(n\alpha (n))$ steps, where $\alpha (n)$ is the very slowly growing inverse Ackermann function defined in [14]. A third algorithm solves a problem of intermediate complexity. We require the answers on-line, but we assume that all tree merging instructions precede the information requests. This algorithm requires $O(n \log \log n)$ time. We apply the first on-line algorithm to a problem in code optimization, that of computing immediate dominators in a reducible flow graph. We show how this computation can be performed in $O(n\log n)$ steps.
Referência(s)