Skip to main content

Disjoint Set Union (Advanced)

Learn Disjoint Set Union (Advanced) (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Disjoint Set Union: Size, Components and Rollback Union-Find keeps groups of elements and answers "are a and b in the same group?". Two optimisations make it almost O(1) per operation: union by size (hang the smaller tree under the larger) and path compression (point every node visited by find straight at the root). Together the cost is O(α(n)) , where α grows so slowly that it is at most 4 for any real input. Track the size of each group and the number of components for free.

More lessons in Advanced Data Structures