212. Why does union by size or rank keep union-find trees shallow?
MediumDisjoint sets
Technical
Show model answer
Union by size attaches the root of the smaller tree under the root of the larger one; union by rank does the same with an upper bound on height. A node's depth increases only when its tree is linked under a tree at least as large, so the size of the tree containing it at least doubles each time.
Sizes can double at most log2 n times, so every tree has height O(log n), and find costs O(log n) worst case even without path compression. Rank is preferred with path compression because compression changes heights but rank remains a valid upper bound.