Close Window

Show Source |    | About   «  17.24. Tries   ::   Contents   ::   17.26. Week 5  »

17.25. Union/FIND

17.25.1. Union/FIND 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
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
} 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)\) Algorithm Visualization


Proficient Saving... Error Saving
Server Error
Resubmit .

. Path Compression


Proficient Saving... Error Saving
Server Error

   «  17.24. Tries   ::   Contents   ::   17.26. Week 5  »

Close Window