Data Structures and Algorithms with Object-Oriented Design Patterns in C++

## 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  shows how the partition

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

Figure: Representing a Partition as a Forest

The trees in Figure  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 pointers to its children, each node of a tree contains only one pointer--a pointer 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  shows how this can be done using an array of pointers. (This figure shows the same partition as in Figure ). The array contains a pointer for each element of the universal set U. Specifically, the array element contains a pointer to 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.

Figure: Finding the Elements of a Partition