Reference no: EM131036661

Ancestor's algorithm

The least common ancestor of two nodes u and ν in a rooted tree T is the node w that is an ancestor of both u and ν and that has the greatest depth in T. In the off-line least-common-ancestors problem, we are given a rooted tree T and an arbitrary set P = {{u, ν}} of unordered pairs of nodes in T, and we wish to determine the least common ancestor of each pair in P. To solve the off-line least-common-ancestors problem, the following procedure performs a tree walk of T with the initial call LCA (T.root). We assume that each node is colored WHITE prior to the walk.

LCA(u)

1 MAKE-SET(u)
2 FIND-SET(u).ancestor = u
3 for each child ν of u in T
4 LCA(ν)
5 UNION(u, ν)
6 FIND-SET(u).ancestor D u
7 u.color = BLACK
8 for each node ν such that {u, ν } ∈P
9 if ν.color = = BLACK
10 print "The least common ancestor of"

u "and" ν "is" FIND-SET(ν).ancestor

a. Argue that line 10 executes exactly once for each pair {u,ν}∈P.

b. Argue that at the time of the call LCA(u), the number of sets in the disjoint-set data structure equals the depth of u in T .

c. Prove that LCA correctly prints the least common ancestor of u and ν for each pair {u, ν} ∈P.

d. Analyze the running time of LCA, assuming that we use the implementation of the disjoint-set data structure in Section 21.3.