Java Reference
In-Depth Information
figure 24.14
The forest after the
union
of trees with
roots 6 and 7
0
1
2
3
4
5
6
7
-1
-1
-1
-1
-1
4
-1
6
0
1
2
3
4
6
5
7
figure 24.15
The forest after the
union
of trees with
roots 4 and 6
0
1
2
3
4
5
6
7
-1
-1
-1
-1
-1
4
4
6
0
1
2
3
4
5
6
7
applications), the running time is computed for a sequence of
M
intermixed
instructions. In the worst case,
M
consecutive operations could take
Θ
(
MN
) time.
Quadratic running time for a sequence of operations is generally unac-
ceptable. Fortunately, there are several ways to easily ensure that this running
time does not occur.
24.4.1
smart union algorithms
We performed the previous
union
s rather arbitrarily by making the second
tree a subtree of the first. A simple improvement is always to make the
smaller tree a subtree of the larger, breaking ties by any method, an
approach called
union-by-size.
The preceding three
union
operations were
all ties, so we can consider that they were performed by size. If the next
operation is
union
(3, 4), the forest shown in Figure 24.16 forms. Had the
size heuristic not been used, a deeper forest would have been formed (three
nodes rather than one would have been one level deeper).
Search WWH ::
Custom Search