Java Reference
In-Depth Information
(a)
X
Y
(b)
X
I
Y
(c)
X
Y
Z
R
(d)
X
Y
Z
J
R
(e)
X
I
Y
Z
R
Figure 14.39: Path compression. The dashed edges represent
head
mappings and the solid edges represent
soln
values.
of Figure 14.38 is illustrated in Figure 14.39.
The initial stage is shown in Figure 14.39(a). The
head
mappings are estab-
lished as shown by the dashed edges from left to right, but C
The path-compressing C
ur
I
nt
has not
yet been called on any node. Thus, each node's
soln
value points to itself.
Figure 14.39(b) shows the results of calling C
ur
I
nt
(
X
). Because of path com-
pression, both
soln
(
X
)and
soln
(
I
) are updated to point to
Y
. In Figure 14.39(c),
the
head
mappings are extended from
Y
,asshownfornodes
Z
through
R
. Fig-
ure 14.39(d) shows the result of a subsequent call of C
ur
I
nt
ur
I
nt
(
Z
), which updates
soln
(
Z
)
=
soln
(
J
)
=
R
. Finally, Figure 14.39(e) shows the result of another call to
C
(
X
). All nodes whose
head
or
soln
pointers are traversed by this call will
have their
soln
values updated to
R
.AsubsequentcallofC
ur
I
nt
on nodes
X
,
Y
,or
Z
immediately returns node
R
.Node
I
's solution was not updated by
previous calls to C
ur
I
nt
ur
I
nt
. An evaluation of C
ur
I
nt
(
I
) after Figure 14.39(e)
jumps to
Y
and then directly to
R
,updating
soln
(
I
)
=
R
.
