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

figure 24.16
The forest formed by
union-by-size, with the
sizes encoded as
negative numbers

0
1
2
3
4
5
6
7

-1
-1
-1
4
-5
4
4
6

0 1 2 4

3 5 6

7

If the union operation is done by size, the depth of any node is never more
than log N . A node is initially at depth 0, and when its depth increases as a
result of a union , it is placed in a tree that is at least twice as large as before.
Thus its depth can be increased at most log N times. (We used this argument
in the quick-find algorithm in Section 24.3.) This outcome implies that the
running time for a find operation is O (log N ) and that a sequence of M opera-
tions takes at most O ( M log N ) time. The tree shown in Figure 24.17 illus-
trates the worst tree possible after 15 union operations and is obtained if all the
unions are between trees of equal size. (The worst-case tree is called a bino-
mial tree . Binomial trees have other applications in advanced data structures.)

Union-by-size guar-
antees logarithmic
finds.

To implement this strategy, we need to keep track of the size of each tree.
Since we are just using an array, we can have the array entry of the root con-
tain the negative of the size of the tree, as shown in Figure 24.16. Thus the ini-
tial representation of the tree with all -1s is reasonable. When a union
operation is performed, we check the sizes; the new size is the sum of the old.
Thus union-by-size is not at all difficult to implement and requires no extra
space. It is also fast on average because, when random union operations are

Instead of -1 being
stored for roots, the
negative of the size
is stored.

figure 24.17
Worst-case tree for
N = 16

0

1 2 4 8

3 5 6 9 10 12

7 11 13 14

15