Register

17.25. Union/FIND¶

17.25.1. Union/FIND¶

17.25.1.1. Disjoint Sets and Equivalence Classes¶

Sometimes we have a collection of objects that we want to divide into separate sets.

17.25.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?

17.25.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
}
}


17.25.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)$

Settings

Saving...
Server Error
Resubmit

.

Settings

Saving...
Server Error
Resubmit