Union by Rank

Union by rank is an optimization for the disjoint set union data structure. It merges sets by attaching the shallower set to the deeper set to minimize tree height.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class DSU {
  int[] parent;
  int[] rank;

  public DSU(int size) {
    parent = new int[size];
    rank = new int[size];
    for (int i = 0; i < size; i++) {
      parent[i] = i;
      rank[i] = 0; 
    }
  }
  
  public int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x]; 
  }  

  public void union(int x, int y) {
    int xr = find(x), yr = find(y);
    if (xr == yr) {
      return;
    }
    
    if (rank[xr] < rank[yr]) {
      parent[xr] = yr; 
    } else if (rank[xr] > rank[yr]) {
      parent[yr] = xr;
    } else {
      parent[yr] = xr;
      rank[xr]++;
    }
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

struct DSU {
  vector<int> parent;
  vector<int> rank;
  
  DSU(int size) {
    parent.assign(size, 0);
    rank.assign(size, 0);
    for (int i = 0; i < size; i++)
      parent[i] = i;
  }

  int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  void union(int x, int y) {
    int xr = find(x), yr = find(y);
    if (xr == yr) return;

    if (rank[xr] < rank[yr]) {
      parent[xr] = yr;
    } else if (rank[xr] > rank[yr]) {
      parent[yr] = xr;
    } else {
      parent[yr] = xr;
      rank[xr]++; 
    }
  }
};

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class DSU:
  def __init__(self, size):
    self.parent = [i for i in range(size)]
    self.rank = [0] * size
    
  def find(self, x):
    if self.parent[x] != x:
      self.parent[x] = self.find(self.parent[x])
    return self.parent[x]

  def union(self, x, y):
    xr, yr = self.find(x), self.find(y)
    if xr == yr:
      return
      
    if self.rank[xr] < self.rank[yr]:
      self.parent[xr] = yr
    elif self.rank[xr] > self.rank[yr]:
      self.parent[yr] = xr
    else:
      self.parent[yr] = xr
      self.rank[xr] += 1

Union by rank balances the tree structure for more efficient union operations.

Union by Rank is an optimization technique for the Disjoint-Set Data Structure. The “rank” represents the depth of the tree for each set. When uniting two sets, the root of the tree with lower rank becomes a child of the root of the tree with higher rank. This minimizes the tree height, making subsequent operations faster.

Algorithm

  1. Initialization: Along with the parent array, initialize a rank array to store the rank of each set. Initially, all ranks are 0.
  2. Union: To merge two sets, compare their ranks and attach the root of the lower-ranked tree to the root of the higher-ranked tree. Update the rank if both have the same rank.
  3. Find: Same as the standard Disjoint-Set find operation.

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class DisjointSet {
  private int[] parent, rank;
  
  public DisjointSet(int size) {
    parent = new int[size];
    rank = new int[size];
    for (int i = 0; i < size; i++) parent[i] = i;
  }

  public int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }

  public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
      if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
      } else if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
      } else {
        parent[rootY] = rootX;
        rank[rootX]++;
      }
    }
  }
}

C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <vector>

class DisjointSet {
public:
  std::vector<int> parent, rank;
  
  DisjointSet(int size) : parent(size), rank(size, 0) {
    for (int i = 0; i < size; ++i) parent[i] = i;
  }
  
  int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }

  void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
      if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
      } else if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
      } else {
        parent[rootY] = rootX;
        rank[rootX]++;
      }
    }
  }
};

Python Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

The time complexity for the union and find operations is almost (O(1)), thanks to the Union by Rank optimization.