find and join Methods

Two elements of the universe are in the same part of the partition if and only if they share the same root node. Since every tree has a unique root, it makes sense to use the root node as the ``handle'' for that tree. Therefore, the find operation takes an element of the universal set and returns the root node of the tree that contains that element. And because of way in which the trees are represented, we can follow the chain of parent pointers to find the root node.

Program  gives the code for the find method of the PartitionAsForest class. The find method takes as its argument an int and returns a Set. The argument specifies the item of the universe that is the object of the search.

  
Program: PartitionAsForest class find method.

The find operation begins at the node array[item] and follows the chain of parent fields to find the root node of the tree that contains the specified item. The result of the method is the root node.

The running time of the find operation is O(d) where d is the depth in the tree of the node from which the search begins. If we don't do anything special to prevent it, the worst case running time is O(N), where N is the size of the universe. The best performance is achieved when every non-root node points to the root node. In this case, the running time is O(1).

Another advantage of having the parent field in each node is that the join operation can be implemented easily and efficiently. For example, suppose we wish to join the two sets and shown in Figure . While there are many possible representations for , it turns out that there are two simple alternatives which can be obtained in constant time. These are shown in Figure . In the first alternative, the root of is made a child of the root of . This can be done in constant time simply by making the parent field of the root of refer to the root of . The second alternative is essentially the same as the first except that the roles of and are exchanged.

  
Figure: Alternatives for joining elements of a partition.

Program  gives the simplest possible implementation for the join operation. The join method of the PartitionAsForest class takes two arguments--both of the references to Sets. Both arguments are required to be references to distinct PartitionTree instances which are contained in the given partition. Furthermore, both of them are required to be root nodes. Therefore, the sets that the arguments represent are disjoint. The method checkArguments makes sure that the arguments satisfy these conditions.

The join operation is trivial and executes in constant time: It simply makes one node the parent of the other. In this case, we have arbitrarily chosen that the node specified by the first argument shall always become the parent.

  
Program: PartitionAsForest class simple join method.

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.