The Initialize Method void Initialize(int n)
{ // One element per set/class/tree
parent = new int[n+1]
for (int e = 1; e < n ; e++)
parent[e] = 0;
}
Union-Find Problem Given a set {1, 2, …, n} of n elements.
Initially each element is in a different set.
{1}, {2}, …, {n}
An intermixed sequence of union and find operations is performed.
A union operation combines two sets into one.
Each of the n elements is in exactly one set at any time.
A find operation identifies the set that contains a particular element.
Application of trees (not binary trees) and simulated pointers. Simple application of simulated pointers; one that does not require an explicit storage management system.
In this application we are concerned with the time taken to perform an intermixed sequence of operations rather than the time for an individual operation.
A Set As A Tree S = {2, 4, 5, 9, 11, 13, 30}
Some possible tree representations: 4 2 9 11 30 5 13 4 2 9 30 5 13 11 11 4 2 9 30 5 13
Result Of A Find Operation find(i) is to identify the set that contains element i.
In most applications of the union-find problem, the user does not provide set identifiers.
The requirement is that find(i) and find(j) return the same value iff elements i and j are in the same set. 4 2 9 11 30 5 13 find(i) will return the element that is in the tree root.
Strategy For find(i) Start at the node that represents element i and climb up the tree until the root is reached.
Return the element in the root.
To climb the tree, each node must have a parent pointer. 4 2 9 30 5 13 11
Possible Node Structure Use nodes that have two fields: element and parent.
Use an array table[] such that table[i] is a pointer to the node whose element is i.
To do a find(i) operation, start at the node given by table[i] and follow parent fields until a node whose parent field is null is reached.
Return element in this root node.
Example 4 2 9 30 5 13 11 1 table[] 0 5 10 15 (Only some table entries are shown.)
Better Representation Use an integer array parent[] such that parent[i] is the element that is the parent of element i. 4 2 9 30 5 13 11 1 parent[] 0 5 10 15 2 9 13 13 4 5 0
Union Operation union(i,j)
i and j are the roots of two different trees, i != j.
To unite the trees, make one tree a subtree of the other.
parent[j] = i
The Initialize Method void Initialize(int n)
{ // One element per set/class/tree
parent = new int[n+1]
for (int e = 1; e < n ; e++)
parent[e] = 0;
}
The Find Method
int Find(int e)
{// Return root of tree containing i
While (parent[e])
e = parent[e];
return e;
}
The Union Method void Union(int i, int j)
{ // Combine trees with roots i and j
parent[j] = i ;
}
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).
Worse than solutions using array or chain Back to the drawing board.
Smart Union Strategies 4 2 9 30 5 13 11 1 7 8 3 22 6 10 20 16 14 12 union(7,13)
Which tree should become a subtree of the other?
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.
Comments