10.1. Union/FIND¶
10.1.1. Disjoint Sets and Equivalence Classes¶
Sometimes we have a collection of objects that we want to divide into separate sets.
10.1.2. Approach¶
Each object initially is a separate node in its own tree.
When two objects are “equivalent”, then add them to the same tree.
Key question: Given two nodes, are they in the same tree?
10.1.3. Parent Pointer Implementation¶
10.1.4. Union/FIND¶
// General Tree implementation for UNION/FIND
public class ParPtrTree {
private int[] array; // Node array
ParPtrTree(int size) {
array = new int[size]; // Create node array
for (int i=0; i<size; i++) {
array[i] = -1; // Each node is its own root to start
}
}
// Merge two subtrees if they are different
public void UNION(int a, int b) {
int root1 = FIND(a); // Find root of node a
int root2 = FIND(b); // Find root of node b
if (root1 != root2) { // Merge two trees
array[root1] = root2;
}
}
// Return the root of curr's tree
public int FIND(int curr) {
while (array[curr] != -1) {
curr = array[curr];
}
return curr; // Now at root
}
}
10.1.5. Weighted Union¶
A key goal is to keep the depth of nodes as shallow as possible (consistent with efficient processing).
Weighted Union rule:
When two trees are unioned, add one with fewer nodes as a child of the root of the tree with more nodes.
Depth is \(O(\log n)\)
