Constant-Time Lowest Common Ancestor Retrieval
Dan Gusfield · Cambridge University Press eBooks · 1997
Introduction We now begin the discussion of an amazing result that greatly extends the usefulness of suffix trees (in addition to many other applications). Definition In a rooted tree T , a node u is an ancestor of a node v if u is on the unique path from the root to v . With this definition a node is an ancestor of itself. A proper ancestor of v refers to an ancestor that is not v . Definition In a rooted tree T , the lowest common ancestor (lca) of two nodes x and y is the deepest node in T that is an ancestor of both x and y . For example, in Figure 8.1 the lca of nodes 6 and 10 is node 5 while the lca of 6 and 3 is 1. The amazing result is that after a linear amount of preprocessing of a rooted tree, any two nodes can then be specified and their lowest common ancestor found in constant time. That is, a rooted tree with n nodes is first preprocessed in O(n) time, and thereafter any lowest common ancestor query takes only constant time to solve, independent of n . Without preprocessing, the best worst-case time bound for a single query is Θ( n ), so this is a most surprising and useful result. The lca result was first obtained by Harel and Tarjan [214] and later simplified by Schieber and Vishkin [393]. The exposition here is based on the later approach.