The disjoint set class - Data Structures and Problem Solving Using Java - page 910

figure 24.19
Path compression
resulting from a
find(14) on the tree
shown in
Figure 24.17

0

1 2 4 8 12 14

3 5 6 9 10 13 15

7 11

has its parent changed to the root. Figure 24.19 shows the effect of path com-
pression after find (14) on the generic worst tree shown in Figure 24.17. With
an extra two parent changes, nodes 12 and 13 are now one position closer to
the root and nodes 14 and 15 are now two positions closer. The fast future
accesses on the nodes pay (we hope) for the extra work to do the path com-
pression. Note that subsequent union s push the nodes deeper.

When union s are done arbitrarily, path compression is a good idea because
of the abundance of deep nodes; they are brought near the root by path com-
pression. It has been proved that when path compression is done in this case, a
sequence of M operations requires at most O ( M log N ) time, so path compres-
sion by itself guarantees logarithmic amortized cost for the find operation.

Path compression
guarantees
logarithmic amor-
tized cost for the
find operation.

Path compression is perfectly compatible with union-by-size. Thus both
routines can be implemented at the same time. However, path compression is
not entirely compatible with union-by-height because path compression can
change the heights of the trees. We do not know how to recompute them effi-
ciently, so we do not attempt to do so. Then the heights stored for each tree
become estimated heights, called ranks, which is not a problem. The resulting
algorithm, union-by-rank, is thus obtained from union-by-height when com-
pression is performed. As we show in Section 24.6, the combination of a
smart union rule and path compression gives an almost linear guarantee on the
running time for a sequence of M operations.

Path compression
and a smart union
rule guarantee
essentially con-
stant amortized
cost per operation
(i.e., a long
sequence can be
executed in almost
linear time).

java implementation

24.5

The class skeleton for a disjoint sets class is given in Figure 24.20, and the
implementation is completed in Figure 24.21. The entire algorithm is amaz-
ingly short.

Disjoint sets are
relatively simple to
implement.