Path Compression And Union by Rank

A combination of two optimization techniques for Disjoint Set Union (DSU)

Path Compression

When finding the root of a set, instead of just returning the root we make every node on the path point directly to the root. This drastically reduces the tree's height, making future operations faster.

How Path Compression Works?

1

Base Case

  • If x == parent[x], this means that the element x is the root of its set. Therefore, x is returned as the result.
2

Recursive Case

  • If x is not the root, the function recursively finds the parent of x by calling find() on parent[x]. This continues until it reaches the root.
3

Path Compression

  • parent[x] = find(parent[x], parent) performs path compression. It directly links x to its root, which helps speed up future queries by flattening the structure of the tree.
Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6

Implementation: Path Compression

//pathCompression.cpp
int find(int x, vector<int> &parent)
{
if (x == parent[x])
    return x;
return parent[x] = find(parent[x], parent);
}

Union By Rank

Union by Rank is an optimization technique used in the Union-Find (DSU) data structure to keep the tree as flat as possible.When two trees are merged (via union), the root of the tree with the smaller rank is made a child of the root of the tree with the larger rank. If both trees have the same rank, one of them becomes the root, and its rank is incremented by 1.

Implementation: Union By Rank

//unionbyRank.cpp
void Union(int a, int b, vector<int> &parent,vector<int> &rank)
{
int a_parent = find(a, parent);
int b_parent = find(b, parent);
if (a_parent == b_parent)
{
    return;
}
else if (rank[a_parent] > rank[b_parent])
{
    parent[b_parent] = a_parent;
}
else if (rank[b_parent] > rank[a_parent])
{
    parent[a_parent] = b_parent;
}
else{
    parent[b_parent]=a_parent;
    rank[a_parent]++;
}
}

Implementation of DSU (Path Compression and Union By Rank)

//dsubypathcompressionandunionbyrank.cpp
#include <iostream>
#include <vector>
using namespace std;
int find(int x, vector<int> &parent)
{
if (x == parent[x])
    return x;
return parent[x] = find(parent[x], parent);
}
void Union(int a, int b, vector<int> &parent,vector<int> &rank)
{
int a_parent = find(a, parent);
int b_parent = find(b, parent);
if (a_parent == b_parent)
{
    return;
}
else if (rank[a_parent] > rank[b_parent])
{
    parent[b_parent] = a_parent;
}
else if (rank[b_parent] > rank[a_parent])
{
    parent[a_parent] = b_parent;
}
else{
    parent[b_parent]=a_parent;
    rank[a_parent]++;
}
}
int main()
{
int n;
cin >> n;
vector<int> parent(n);
vector<int> rank(n,0);
for (int i = 0; i < n; i++)
{
    parent[i] = i;
}
Union(0, 1, parent,rank);
Union(3, 4, parent,rank);
Union(0, 3, parent,rank);
 for (int i = 0; i < n; i++) {
    find(i, parent); 
}
for (int &ele : parent)
{
    cout << ele << " ";
}
}