Union Find

Definitions

1. A data structure (also called Disjoint Set Union) that tracks a collection of non-overlapping sets, supporting two near-constant-time operations: `find` (determine which set an element belongs to) and `union` (merge two sets). With path compression and union by rank optimizations, both operations run in amortized O(α(n)) time. It is the backbone of Kruskal's MST algorithm and connected-component detection.

   In plain English: A data structure that efficiently groups items into sets and quickly answers 'are these two items in the same group?'

   Example: "We used union-find to detect connected components in the social graph — merging friend groups runs in nearly O(1) per operation."

Related Terms

• Hash Map
• Hash Ring
• Hash Set
• Hashing Algorithm
• Priority Queue
• Radix Tree
• Search Tree
• Segment Tree
• Skiplist