Java Reference
In-Depth Information
F
J
5
0
0
5
5
5
0
5
A
B
C
D
E
F
G
H
I
J
9
0
1
2
3
4
5
6
7
8
A
G
I
D
E
B
C
H
Figure6.8 An example of path compression, showing the result of processing
equivalence pair (H, E) on the representation of Figure 6.7(c).
Example6.4 Figure 6.7(d) shows the result of processing equivalence
pair (H, E) on the the representation shown in Figure 6.7(c) using the stan-
dard weighted union rule without path compression. Figure 6.8 illustrates
the path compression process for the same equivalence pair. After locating
the root for node H, we can perform path compression to make H point
directly to root object A. Likewise, E is set to point directly to its root, F.
Finally, object A is set to point to root object F.
Note that path compression takes place during the FIND operation, not
during the UNION operation. In Figure 6.8, this means that nodes B, C, and
H have node A remain as their parent, rather than changing their parent to
be F. While we might prefer to have these nodes point to F, to accomplish
this would require that additional information from the FIND operation be
passed back to the UNION operation. This would not be practical.
Path compression keeps the cost of each FIND operation very close to constant.
To be more precise about what is meant by “very close to constant,” the cost of path
compression for n FIND operations on n nodes (when combined with the weighted
union rule for joining sets) is approximately 1 (n log n). The notation “log n”
means the number of times that the log of n must be taken before n 1. For
example, log 65536 is 4 because log 65536 = 16, log 16 = 4, log 4 = 2, and
finally log 2 = 1. Thus, log n grows very slowly, so the cost for a series of n FIND
operations is very close to n.
Note that this does not mean that the tree resulting from processing n equiva-
lence pairs necessarily has depth (log n). One can devise a series of equivalence
operations that yields (log n) depth for the resulting tree. However, many of the
equivalences in such a series will look only at the roots of the trees being merged,
requiring little processing time. The total amount of processing time required for
n operations will be (n log n), yielding nearly constant time for each equiva-
1 To be more precise, this cost has been found to grow in time proportional to the inverse of
Ackermann's function. See Section 6.6.
 
Search WWH ::




Custom Search