Optimizing Union-Find: Rank and Size Heuristics

Welcome back! In our previous lesson, we significantly improved our Union-Find data structure by implementing the path compression optimization for the find operation. This technique flattens the trees after they've grown, making subsequent lookups faster.

Today, we'll address the other side of the coin. Instead of just fixing tall trees, we will prevent them from forming in the first place. The learning outcome for this lesson is to implement the union by rank/size optimization to keep the internal tree structures balanced. This heuristic is applied during the union operation and, when combined with path compression, creates an exceptionally efficient data structure.

The Problem with Naive Union

Let's revisit the core issue. A naive union(x, y) operation might always attach the tree containing y to the root of the tree containing x. While simple, this can be disastrous for performance.

Consider uniting three elements: 0, 1, and 2.

• A naive union(0, 1) might make 1 the parent of 0.
• A subsequent union(1, 2) might make 2 the parent of 1.

The result is a tall, skinny chain: 0 -> 1 -> 2. A find(0) call now has to traverse two links. This is the exact problem path compression helps solve, but a smarter union operation can avoid creating such imbalanced structures from the start.

The smarter approach is based on a simple, powerful heuristic: when merging two trees, always attach the smaller tree to the root of the larger tree. This intuitively keeps the overall height of the resulting tree from growing unnecessarily.

The video segment below offers a great explanation of why this strategy is so effective.

We can measure "smaller" and "larger" in two primary ways: by rank (a proxy for height) or by size (the number of nodes).

Union by Rank

In this approach, we maintain an extra array, rank, where rank[i] stores an upper bound on the height of the tree rooted at i.

Initialization:

• Each element starts in its own set.
• The parent of each element is itself.
• The rank of each element is initialized to 0.

The union Logic:

1. Find the roots of the two elements to be merged, let's call them root_a and root_b.
2. If root_a and root_b are the same, the elements are already in the same set. Do nothing.
3. Compare their ranks: rank[root_a] vs. rank[root_b].
   • If rank[root_a] < rank[root_b], attach the smaller tree to the larger one by setting parent[root_a] = root_b. The rank of root_b remains unchanged.
   • If rank[root_a] > rank[root_b], do the opposite: parent[root_b] = root_a. The rank of root_a remains unchanged.
   • If rank[root_a] == rank[root_b], it doesn't matter which tree we attach to which. Let's say we set parent[root_b] = root_a. Since we've attached a tree of equal rank, the height of the resulting tree increases by one. We must therefore increment the rank of the new root: rank[root_a]++.

This logic ensures that the tree height only grows when we merge two trees of the exact same rank.

The following resource provides a clear C++ implementation of this logic.

Union by Size

An equally effective and often more intuitive alternative is to track the size of each component (the number of nodes) instead of its rank. We use a size array for this.

Initialization:

• The parent of each element is itself.
• The size of each element is initialized to 1.

The union Logic:

1. Find the roots of the two elements, root_a and root_b.
2. If they are already in the same set, do nothing.
3. Compare their sizes: size[root_a] vs. size[root_b].
   • Always attach the root of the smaller component to the root of the larger one. For instance, if size[root_a] < size[root_b], set parent[root_a] = root_b.
   • Crucially, update the size of the new root by adding the size of the component that was just attached. In our example, size[root_b] += size[root_a]. This update happens every time a merge occurs.

The take U forward video provides a fantastic walkthrough of Union by Size, from concept to code.

Rank vs. Size: Which to Use?

Both optimizations have the same excellent amortized time complexity. In practice, you can use either.

• Union by Size can be slightly more intuitive, as "size" is a concrete property (number of nodes), whereas "rank" is a more abstract upper bound on height that can become inaccurate due to path compression.
• Some problems might require you to know the size of a component, making Union by Size a natural choice.

Unless a problem specifies otherwise, the choice is a matter of personal preference.

The Complete Picture: Combining Both Optimizations

The true power of the Union-Find data structure is unlocked when we use Path Compression (from our last lesson) and Union by Rank/Size (from this lesson) together.

• Path Compression optimizes the find operation by flattening the tree on the fly.
• Union by Rank/Size optimizes the union operation by proactively building balanced trees.

When combined, the amortized time complexity for both find and union becomes nearly constant, technically O($\alpha (N)$), where $\alpha (N)$ is the extremely slow-growing Inverse Ackermann function. For any practical input size N in an interview setting, $\alpha (N)$ is less than 5, making the operations effectively constant time.

Here is a full C++ implementation of a DisjointUnionSets class that incorporates both path compression and union by rank.

Conclusion

In this lesson, we completed our optimization of the Union-Find data structure. By implementing the Union by Rank/Size heuristic, we ensure that the trees representing our disjoint sets remain short and balanced, preventing the worst-case scenarios that can plague a naive implementation.

Key Takeaways:

• Motivation: The Union by Rank/Size optimization prevents the creation of tall, skewed trees during union operations.
• Heuristic: Always attach the smaller tree to the root of the larger tree.
• Metrics: "Size" can be measured by rank (an upper bound on height) or by the size (number of nodes in the component).
• Implementation (Rank): If ranks are equal, the new root's rank is incremented. Otherwise, ranks are unchanged.
• Implementation (Size): The new root's size is always increased by the size of the merged component.
• Synergy: Combining Union by Rank/Size with Path Compression yields a nearly constant time complexity for Union-Find operations.

You are now equipped with the theory and implementation of a fully optimized Union-Find data structure. In our next lesson, we will put it to use in a classic application: applying Union-Find to determine the number of connected components in a graph.