Processing math: 100%

9.Disjoint Sets and Equivalence Classes§

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

Created with Raphaël 2.1.2
A
B
C
D
E
F
G
H
I
J

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

  1. 5
  2. 0
  3. 0
  4. 5
  5. 3
  6. /
  7. 5
  8. 2
  9. 5
  10. /
  1. A0
  2. B1
  3. C2
  4. D3
  5. E4
  6. F5
  7. G6
  8. H7
  9. I8
  10. J9
Created with Raphaël 2.1.2
A
B
C
D
E
F
G
H
I
J

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(logn)

Algorithm Visualization

1 / 42 Settings
<<<>>>

We will now demonstrate a series of UNION operations

  1. A0
  2. B1
  3. C2
  4. D3
  5. E4
  6. F5
  7. G6
  8. H7
  9. I8
  10. J9
  1. /
  2. /
  3. /
  4. /
  5. /
  6. /
  7. /
  8. /
  9. /
  10. /
  • 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 with weighted union
  • if (weights[root2] > weights[root1]) {
  • array[root1] = root2;
  • weights[root2] += weights[root1];
  • } else {
  • array[root2] = root1;
  • weights[root1] += weights[root2];
  • }
  • }
  • }
Created with Raphaël 2.1.2
A
B
C
D
E
F
G
H
I
J
Proficient Saving... Error Saving
Server Error
Resubmit

.

.

Path Compression

1 / 12 Settings
<<<>>>

We will show how to union nodes (H) and (E) with path compression

  1. /
  2. 0
  3. 0
  4. 5
  5. 3
  6. /
  7. 5
  8. 2
  9. 5
  10. /
  1. A0
  2. B1
  3. C2
  4. D3
  5. E4
  6. F5
  7. G6
  8. H7
  9. I8
  10. J9
Created with Raphaël 2.1.2
A
B
C
D
E
F
G
H
I
J
Proficient Saving... Error Saving
Server Error
Resubmit