Union-find and disjoint sets

A tree for GROUPING, not searching. Merge groups + test "same group?" in ≈ constant time.

Sets as trees named by their root

• Each element points to a parent; root = the group's name
• Same group ⟺ same root
• Union by rank: attach shorter tree under taller
• Path compression: on find, point everything straight at the root

Watch merges + path compression

Merge pairs → fours → one. Then find(7) compresses the path to the root. The structure flattens itself as you use it.

O(α(n)) — near constant

α(n) ≤ 4 for any real n. 566× faster than naive O(n)-union at n=16000.

Merge only, never split

• No efficient "un-union" (compression scrambled the tree)
• Answers one question — "same group?" — as fast as anything can
• Both optimizations needed together for the α(n) bound

Takeaway

A few lines beat a 566× hardware speedup — the wins are algorithmic. Drives Kruskal, connected components, cycle detection. Next tier: graphs.