Disjoint Sets (Union-Find)
Interactive visualization of disjoint set data structure with union by size and path compression
Controls
Array Representation
Array Values:
- Negative value: Root node, absolute value = set size
- Non-negative value: Index of parent node
- Empty (-): Element not yet inserted
Set Visualization
No elements inserted yet. Start by inserting elements!
Operations
Insert(x)
Creates a new singleton set containing element x. Sets array[x] = -1.
Union(x, y)
Merges the sets containing x and y. Uses union by size: smaller tree becomes child of larger tree. Tie-breaker: If equal size, first parameter (x) becomes parent.
Find(x)
Returns the root of the set containing x. Uses path compression to flatten the tree structure (applied automatically during Union).
Disjoint Set Data Structure
Purpose: Efficiently manages a collection of disjoint (non-overlapping) sets.
Union by Size: Always attach the smaller tree to the root of the larger tree to keep trees shallow.
Path Compression: During find operations, make every node point directly to the root for future efficiency.
Time Complexity: Nearly O(1) amortized time per operation (inverse Ackermann function).
Applications: Kruskal's MST algorithm, cycle detection, connected components.