文档介绍：算法和数据结构10
Applications
Union-Find Problem
Union-Find Problem
Given a set {1, 2, …, n} of n elements.
Initialt node.
The Union Method
public void union(int rootA, int rootB)
{parent[rootB] = rootA;}
Time Complexity Of union()
O(1)
Time Complexity of find()
Tree height may equal number of elements in tree.
union(2,1), union(3,2), union(4,3), union(5,4)…
2
1
3
4
5
So complexity is O(u).
u Unions and f Find Operations
O(u + uf) = O(uf)
Time to initialize parent[i] = 0 for all i is O(n).
Total time is O(n + uf).
Back to the drawing board.
Height Rule
Make tree with smaller height a subtree of the other tree.
Break ties arbitrarily.
4
2
9
30
5
13
11
1
7
8
3
22
6
10
20
16
14
12
union(7,13)
Weight Rule
Make tree with fewer number of elements a subtree of the other tree.
Break ties arbitrarily.
4
2
9
30
5
13
11
1
7
8
3
22
6
10
20
16
14
12
union(7,13)
Implementation
Root of each tree must record either its height or the number of elements in the tree.
When a union is done using the height rule, the height increases only when two trees of equal height are united.
When the weight rule is used, the weight of the new tree is the sum of the weights of the trees that are united.
Height Of A Tree
If we start with single element trees and perform unions using either the height or the weight rule. The height of a tree with p elements is at most floor (log2p) + 1.
Proof is by induction on p. See text.
Sprucing Up The Find Method
find(1)
Do additional work to make future finds easier.
12
14
20
10
22
a
4
2
9
30
5
13
11
1
7
8
3
6
16
b
c
d
e
f
g
a, b, c, d, e, f, and g are subtrees
Path Compaction
Make all nodes on find path point to tree root.
find(1)
12
14
20
10
22
a
4
2
9
30
5
13
11
1
7
8
3
6
16
b
c
d
e
f
g
a, b, c, d, e, f, and g are subtrees
Makes two passes up the tree.
Path Splitting
Nodes on f