The disjoint set class - Data Structures and Problem Solving Using Java - page 906

Each set is represented by a tree (recall that a collection of trees is
called a forest ). The name of a set is given by the node at the root. Our trees
are not necessarily binary trees, but their representation is easy because the
only information we need is the parent. Thus we need only an array of inte-
gers: Each entry p[i] in the array represents the parent of element i , and we
can use -1 as a parent to indicate a root. Figure 24.12 shows a forest and the
array that represents it.

A tree is repre-
sented by an array
of integers repre-
senting parent
nodes. The set
name of any node
in a tree is the root
of a tree.

To perform a union of two sets, we merge the two trees by making the root
of one tree a child of the root of the other. This operation clearly takes con-
stant time. Figures 24.13-24.15 represent the forest after each of union (4, 5),
union (6, 7), and union (4, 6), where we have adopted the convention that the
new root after union ( x, y ) is x .

The union opera-
tion is constant
time.

A find operation on element x is performed by returning the root of the tree
containing x . The time for performing this operation is proportional to the number
of nodes on the path from x to the root. The union strategy outlined previously
enables us to create a tree whose every node is on the path to x, resulting in a
worst-case running time of Θ ( N ) per find . Typically (as shown in the preceding

The cost of a find
depends on the
depth of the
accessed node and
could be linear.

figure 24.12
A forest and its eight
elements, initially in
different sets

0
1
2
3
4
5
6
7

-1
-1
-1
-1
-1
-1
-1
-1

0 1 2 3 4 5 6 7

figure 24.13
The forest after the
union of trees with
roots 4 and 5

0
1
2
3
4
5
6
7

-1
-1
-1
-1
-1
4
-1
-1

0 1 2 3 4 6 7

5