Advanced · Module 18 · Lesson 2 of 4
Union by rank and path compression
Attaching the smaller tree under the larger keeps trees logarithmically shallow, and pointing every visited node straight at the root flattens them further. Together they make union-find's operations nearly constant time.
By the end you can
- Keep union-find trees shallow with union by size or rank, and explain the log n height bound
- Implement path compression, and path halving as a one-pass alternative
- Explain what the inverse Ackermann bound means in practice
Builds on Disjoint sets.
01 · A question first
Unions in an unlucky order turn a union-find forest into a chain n long, and every find walks the whole chain. Two small changes, one in union and one in find, make the cost per operation so close to constant that it never exceeds about 4 steps for any input you could ever store. What are they?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Why trees grow tall
- Fix 1: union by size or rank
- Fix 2: path compression
- Nearly constant time
- Seeing union by size work
- The two fixes together
- Testing a union-find
- The template
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem