Java Reference
In-Depth Information
node, (
u, v
) is in the pair list and we have already finished the recursive call to
v
, we have enough information to determine NCA(
u, v
).
Figure 24.9 helps in understanding how this algorithm works. Here, we
are about to finish the recursive call to
D
. All shaded nodes have been visited
by a recursive call, and except for the nodes on the path to
D,
all the recursive
calls have already finished. We mark a node after its recursive call has been
completed. If
v
is marked, then NCA(
D, v
) is some node on the path to
D.
The
anchor
of a visited (but not necessarily marked) node
v
is the node on the cur-
rent access path that is closest to
v
. In Figure 24.9,
p
's anchor is
A, q
's anchor
is
B,
and
r
is unanchored because it has yet to be visited; we can argue that
r
's
anchor is
r
at the point that
r
is first visited. Each node on the current access
path is an anchor (of at least itself ). Furthermore, the visited nodes form
equivalence classes: Two nodes are related if they have the same anchor, and
we can regard each unvisited node as being in its own class. Now suppose
once again that (
D, v
) is in the pair list. Then we have three cases.
The
anchor
of a vis-
ited (but not neces-
sarily marked) node
v
is the node on the
current access path
that is closest to
v
.
1.
v
is unmarked, so we have no information to compute NCA(
D, v
).
However, when
v
is marked, we are able to determine NCA(
v, D
).
2.
v
is marked but not in
D
's subtree, so NCA(
D, v
) is
v
's anchor.
3.
v
is in
D
's subtree, so NCA(
D, v
) =
D
. Note that this is not a special
case because
v
's anchor is
D
.
All that remains to be done is to ensure that, at any instant, we can deter-
mine the anchor of any visited node. We can easily do so with the union/find
algorithm. After a recursive call returns, we call
union
. For instance, after the
recursive call to
D
in Figure 24.9 returns, all nodes in
D
have their anchor
The union/find
algorithm is used to
maintain the sets of
nodes with com-
mon anchors.
figure 24.9
The sets immediately
prior to the return
from the recursive call
to
D
;
D
is marked as
visited and
NCA(
D, v
)
is
v
's anchor to the
current path.
A
B
p
C
q
D
r
Search WWH ::
Custom Search