|
|
Tarjan's Off-line Least Common Ancestors AlgorithmIn computer science, Tarjan's off-line least common ancestors algorithm is an algorithm based on the least common ancestor property. The least common ancestor of two nodes d and e in a rooted tree T is the node g that is an ancestor of both d and e and that has the greatest depth in T. The off-line least common ancestors problem gives us a rooted tree T and a set P = of unordered pairs of nodes in T. Tarjan's off-line least common ancestors algorithm determines the least common ancestor of each pair in P. An example of the algorithm: TOLCA(u) { Make-set(u); ancestorFind-Set(u) <- u; for each child v in u in T do { TOLCA(v); Union(u,v); ancestorFind-Set(u) <- u; } colouru <- black; for each node v such that {u,v} in P do if (colourv = black) { print "Tarjan's Least Common Ancestor of" + u + " and " + v + " is " ancestorFind-Set(v); } } The following procedure assumes each node is white before coloured black.
|
 |