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

Implementing a Partition using a Forest

 

A partition is a set of sets. Consequently, there are two related issues to consider when developing an approach for representing partitions:

  1. How are the individual elements or parts of the partition represented?
  2. How are the elements of a partition combined into the whole?
This section presents an approach in which each element of a partition is a tree. Therefore, the whole partition is a forest .

For example, Figure gif shows how the partition

eqnarray27910

can be represented using a forest. Notice that each element of the universal set tex2html_wrap_inline66554 appears in exactly one node of exactly one tree.

   figure27912
Figure: Representing a partition as a forest.

The trees in Figure gif have some very interesting characteristics. The first characteristic concerns the shapes of the trees: The nodes of the trees have arbitrary degrees. The second characteristic concerns the positions of the keys: there are no constraints on the positions of the keys in a tree. The final characteristic has to do with the way the tree is represented: Instead of pointing to its children, each node of the tree points to its parent!

Since there is no particular order to the nodes in the trees, it is necessary to keep track of the position of each node explicitly. Figure gif shows how this can be done using an array. (This figure shows the same partition as in Figure gif). The array contains a node for each element of the universal set U. Specifically, the tex2html_wrap_inline57340 array element holds the node that contains item i. Having found the desired node, we can follow the chain of parent pointers to find the root of the corresponding tree.

   figure28138
Figure: Finding the elements of a partition.




next up previous contents index

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