Optimizations in Union Find Data Structure

A union-find data structure is also called disjoined set data structure as it a collection of disjoined subsets.

This table summarizes the optimizations in Union Find data structure (explained in detail further into this OpenGenus article):

Time complexity
Case




O(n)
No updation of parent pointer in Find + No control of tree heights in Union


O(m lg(n))
No updation of parent pointer in Find + use of rank in Union


O(log*(n))
Union by Rank/Size


O(α(n))
Path compression + union using si...