9.Disjoint Sets and Equivalence Classesยง
Sometimes we have a collection of objects that we want to divide into separate sets.
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?
Parent Pointer Implementation
Union/FIND
// General Tree implementation for UNION/FIND
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
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
int FIND(int curr) {
if (array[curr] == -1) return curr; // At root
while (array[curr] != -1) curr = array[curr];
return curr;
}
}
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 union'ed, add one with fewer nodes as a child of the root of the tree with more nodes.
- Depth is \(O(\log n)\)
Algorithm Visualization
.
.