Java Reference
In-Depth Information
/
**
GeneralTreeclassimplementationforUNION/FIND
*
/
classParPtrTree{
privateInteger[]array; //Nodearray
publicParPtrTree(intsize){
array=newInteger[size]; //Createnodearray
for(inti=0;i<size;i++)
array[i]=null;
}
/
**
Determineifnodesareindifferenttrees
*
/
publicbooleandiffer(inta,intb){
Integerroot1=FIND(a); //Findrootofnodea
Integerroot2=FIND(b); //Findrootofnodeb
returnroot1!=root2; //Compareroots
}
/
**
Mergetwosubtrees
*
/
publicvoidUNION(inta,intb){
Integerroot1=FIND(a); //Findrootofnodea
Integerroot2=FIND(b); //Findrootofnodeb
if(root1!=root2)array[root2]=root1;//Merge
}
/
**
@returnTherootofcurr'stree
*
/
publicIntegerFIND(Integercurr){
if(array[curr]==null)returncurr;//Atroot
while(array[curr]!=null)curr=array[curr];
returncurr;
}
Figure6.4
General tree implementation using parent pointers for the UNION/
FIND algorithm.
is given two new methods,
differ
and
UNION
. Method
differ
checks if two
objects are in different sets, and method
UNION
merges two sets together. A private
method
FIND
is used to find the ultimate root for an object.
An application using the UNION/FIND operations should store a set of n ob-
jects, where each object is assigned a unique index in the range 0 to n 1. The
indices refer to the corresponding parent pointers in the array. Class
ParPtrTree
creates and initializes the UNION/FIND array, and methods
differ
and
UNION
take array indices as inputs.
Figure 6.5 illustrates the parent pointer implementation. Note that the nodes
can appear in any order within the array, and the array can store up to n separate
trees. For example, Figure 6.5 shows two trees stored in the same array. Thus,
a single array can store a collection of items distributed among an arbitrary (and
changing) number of disjoint subsets.
Consider the problem of assigning the members of a set to disjoint subsets
called equivalence classes. Recall from Section 2.1 that an equivalence relation is
