Source: CS 225 Lecture, G. Carl Evans | Course: Data Structures, UIUC
Tags: disjoint sets, union-find, up-trees, union by rank, union by size, union by height, CS 225, data structures, UIUC
Difficulty: Intermediate | Prerequisites: Basic tree structures, arrays, recursion, Big-O notation.
Disjoint sets (also called union-find) let you track which elements belong to the same group and merge groups efficiently. This is one of the foundational data structures in graph algorithms: you will use it for Kruskal's minimum spanning tree, connected components, and cycle detection. The structure stores a collection of non-overlapping sets and supports two core operations, find (which set does this element belong to?) and union (merge two sets into one). If you are comfortable with arrays, recursion, and basic tree shapes, you have what you need.
Disjoint sets use an array of up-trees to represent non-overlapping groups. Each element points to its parent; roots store a negative value to mark themselves. Two optimisations, smart union and path compression, keep the trees nearly flat, giving an amortised cost per operation that is effectively constant.
Disjoint sets (union-find)
A data structure that stores a collection of non-overlapping sets and supports merging sets together and querying which set an element belongs to. In simple terms, it answers "are these two things in the same group?" and lets you combine groups.
UpTree
The tree representation used inside a disjoint set. Every node stores a pointer to its parent. The root of each tree is the representative (identity) of that set. Think of it as a tree where arrows point upward to the parent, instead of downward to children.
Find
The operation that returns the root (representative) of the set containing a given element. It works by following parent pointers up the tree until it reaches a node pointing to itself.
Union
The operation that merges two sets into one by making the root of one tree point to the root of the other.
Smart union
A strategy for choosing which root becomes the child during a union, so the resulting tree stays balanced. The two variants are union by height and union by size.
Union by height
Always attach the shorter tree under the taller tree's root. The root's stored value tracks the height (as a negative number). Keeps the maximum height of any tree at O(log n).
Union by size
Always attach the smaller tree (fewer nodes) under the larger tree's root. The root's stored value tracks the number of elements (as a negative number). Also guarantees O(log n) height.
Path compression
An optimisation applied during find: after locating the root, every node visited along the path is re-pointed directly to the root. This flattens the tree for future queries.
Rank
An upper bound on the height of a node's subtree. When path compression is used alongside union by height, the stored "height" may no longer reflect the true height, so it is called rank instead.
Iterated logarithm (log*n)
The number of times you can take the logarithm of n before the result drops to 1 or below. It grows extraordinarily slowly: log*(2^65536) = 5.
Inverse Ackermann function, α(m, n)
An even slower-growing function than log*n. It appears in the tightest amortised bound for disjoint sets with both smart union and path compression. For all practical input sizes, α(m, n) ≤ 4.
A disjoint set with n elements is stored in a single integer array s[] of size n. Each index represents one element.
If s[i] is non-negative, element i's parent is s[i].
If s[i] is negative, element i is the root of its set.
Under union by height, the stored value is -(height + 1). A singleton root stores -1.
Under union by size, the stored value is -(number of elements in the set). A singleton root stores -1.
For example, given four sets {2,5,9}, {7}, {0,1,4,8}, {3,6} the array might look like:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
Value | 4 | 8 | 5 | -1 | -1 | -1 | 3 | -1 | 4 | 5 |
Reading the array: element 0 has parent 4, element 4 stores -1 so it is a root. Following 0 → 4 tells you element 0 is in the set whose representative is 4. Indices 3, 4, 5, and 7 are all roots (negative values), each heading its own set.
Find follows parent pointers from a given element up to the root:
int DisjointSets::find(int i) {
if ( s[i] < 0 ) { return i; }
else { return find( s[i] ); }
}The base case: if s[i] is negative, i is the root, so return i. Otherwise recurse on the parent. Without any optimisations, this takes O(h) time where h is the height of the tree.
Naive union (just make one root point to the other with no rule) can produce a degenerate chain of height n. Smart union prevents this.
Union by height
Goal: keep the tree as short as possible.
Rule: attach the shorter tree's root under the taller tree's root.
When two trees have equal height, pick either as the new root and increment its height by 1.
The root stores -(height + 1). A single node has height 0, stored as -1. A root of height 3 stores -4 (under union-by-height encoding; under union-by-size encoding -4 would mean 4 elements, so pay attention to which scheme is in use).
Union by size
Goal: minimise the number of nodes whose depth increases.
Rule: attach the smaller set's root under the larger set's root.
The root stores the negative of the set's element count. A singleton stores -1; a set of 8 elements stores -8.
Both strategies give the same height guarantee: any tree on n elements has height at most O(log n).
Worked example (from lecture)
Two trees: one rooted at 7 (nodes 0,1,2,3,6,7,8,9, height 3) and one rooted at 4 (nodes 4,5,10,11, height 3).
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
By height | Value | 6 | 6 | 6 | 8 | -4 | 10 | 7 | -3 | 7 | 7 | 4 | 5 |
By size | Value | 6 | 6 | 6 | 8 | -8 | 10 | 7 | -4 | 7 | 7 | 4 | 5 |
Notice the root values differ: union by height stores -(height+1), union by size stores -(element count).
Union by size: height ≤ O(log n)
We prove the contrapositive: a tree of height h must contain at least 2^h nodes, which means h ≤ log₂(n).
Base case: a single node has height 0 and 2⁰ = 1 node. ✓
Inductive hypothesis: assume any tree built by union-by-size with height k contains at least 2^k nodes.
Case 1 (unequal heights): if two trees of different height are unioned, the shorter one goes under the taller root. The result's height is unchanged (it is the taller tree's height), and the node count has increased. The bound still holds.
Case 2 (equal heights): both trees have height k and each has at least 2^k nodes. The merged tree has height k+1 and at least 2^k + 2^k = 2^(k+1) nodes. The bound holds by induction.
Union by height: the same bound
The proof is analogous. We show a tree with root of height k has at least 2^k nodes. The only case that increases the height is when two trees of equal height k are merged, giving height k+1 and at least 2·2^k = 2^(k+1) nodes.
The upshot: with either smart union strategy and no path compression, find runs in O(log n) worst case.
Students often confuse the sign convention for roots. A root value of -3 means height 2 under union-by-height encoding, but 3 elements under union-by-size encoding. Always check which scheme is in use before interpreting the array.
Students sometimes think union by height and union by size produce identical trees. They do not. The trees can differ, even though both guarantee O(log n) height.
Students assume find modifies the array when no path compression is used. The basic find above is read-only; only the path-compression variant writes.
Students forget that the root stores metadata (height or size), and try to use the negative value as a parent pointer.
⚠️ You will be asked to trace through find and union on a given array. Practise reading an array, drawing the corresponding up-trees, performing a union, and writing the updated array.
⚠️ Know both union-by-height and union-by-size encoding conventions and be able to distinguish them from a given array.
⚠️ The inductive proof that height ≤ O(log n) is a classic exam question (base case, inductive step, both cases).
⚠️ Be able to state the running time of find with smart union only (O(log n) per operation).
True or false: in the standard array representation, a negative value at index i means i is a root. True.
Fill in the blank: union by height attaches the ______ tree under the ______ tree. shorter; taller.
True or false: union by size and union by height always produce the same tree structure. False.
Fill in the blank: with smart union and no path compression, find is O(______). log n.
True or false: a root storing -5 under union-by-size means the set has 5 elements. True.
Q: Given the array [4, 8, 5, -1, -1, -1, 3, -1, 4, 5], what is find(0)?
A: Follow 0 → s[0]=4 → s[4]=-1, so find(0) = 4.
Q: Using union by height, you union the set rooted at 7 (height 2) with the set rooted at 4 (height 3). Which root becomes the child?
A: 7 becomes the child of 4, because 7's tree is shorter. Set s[7] = 4.
Q: Two sets both have height 2 under union by height. After unioning them, what is the height of the resulting tree?
A: 3. When heights are equal, the merged tree's height increases by 1.
Q: What value does the root store after a union-by-size merge of a set with 3 elements and a set with 5 elements?
A: -8. The combined set has 8 elements, stored as -(3+5) = -8.
Q: In the inductive proof for union by size, what is the base case?
A: A single-node tree has height 0 and contains 2⁰ = 1 node, satisfying n ≥ 2^h.
Disjoint sets are a core building block for Kruskal's algorithm (minimum spanning trees), where you need to check whether adding an edge would create a cycle. They also appear in connected-component labelling on graphs and in network connectivity problems. The inductive proof style used for the height bound is the same approach you will see in proofs about binary heaps and balanced BSTs.
disjoint sets, union-find, up-tree, uptree, union by rank, union by height, union by size, smart union, weighted union, find operation, path compression, inverse Ackermann, iterated logarithm, log star, amortised analysis, Kruskal, connected components, CS 225, UIUC, data structures, equivalence classes