Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

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 gif 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.

   program28460
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 tex2html_wrap_inline59252 and tex2html_wrap_inline59256 shown in Figure gif. While there are many possible representations for tex2html_wrap_inline66596, it turns out that there are two simple alternatives which can be obtained in constant time. These are shown in Figure gif. In the first alternative, the root of tex2html_wrap_inline59256 is made a child of the root of tex2html_wrap_inline59252. This can be done in constant time simply by making the parent field of the root of tex2html_wrap_inline59256 refer to the root of tex2html_wrap_inline59252. The second alternative is essentially the same as the first except that the roles of tex2html_wrap_inline59252 and tex2html_wrap_inline59256 are exchanged.

   figure28476
Figure: Alternatives for joining elements of a partition.

Program gif 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.

   program28799
Program: PartitionAsForest class simple join method.


next up previous contents index

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