Java Reference
In-Depth Information
ditional processing to be worth the effort, so we must settle for getting as close as
possible.
A low-cost approach to reducing the height is to be smart about how two trees
are joined together. One simple technique, called the weighted union rule, joins
the tree with fewer nodes to the tree with more nodes by making the smaller tree's
root point to the root of the bigger tree. This will limit the total depth of the tree to
O(log n), because the depth of nodes only in the smaller tree will now increase by
one, and the depth of the deepest node in the combined tree can only be at most one
deeper than the deepest node before the trees were combined. The total number
of nodes in the combined tree is therefore at least twice the number in the smaller
subtree. Thus, the depth of any node can be increased at most log n times when n
equivalences are processed.
Example6.3
When processing equivalence pair (I, F) in Figure 6.7(b),
F is the root of a tree with two nodes while I is the root of a tree with only
one node. Thus, I is set to point to F rather than the other way around.
Figure 6.7(c) shows the result of processing two more equivalence pairs:
(H, A) and (E, G). For the first pair, the root for H is C while the root
for A is itself. Both trees contain two nodes, so it is an arbitrary decision
as to which node is set to be the root for the combined tree. In the case
of equivalence pair (E, G), the root of E is D while the root of G is F.
Because F is the root of the larger tree, node D is set to point to F.
Not all equivalences will combine two trees. If equivalence (F, G) is processed
when the representation is in the state shown in Figure 6.7(c), no change will be
made because F is already the root for G.
The weighted union rule helps to minimize the depth of the tree, but we can do
better than this. Path compression is a method that tends to create extremely shal-
low trees. Path compression takes place while finding the root for a given node X.
Call this root R. Path compression resets the parent of every node on the path from
X to R to point directly to R. This can be implemented by first finding R. A second
pass is then made along the path from X to R, assigning the parent field of each
node encountered to R. Alternatively, a recursive algorithm can be implemented as
follows. This version of
FIND
not only returns the root of the current node, but
also makes all ancestors of the current node point to the root.
publicIntegerFIND(Integercurr){
if(array[curr]==null)returncurr;//Atroot
array[curr]=FIND(array[curr]);
returnarray[curr];
}
