Nothing special here. It’s just a blog post for summarising my algorithm learning course.
- Part 1 - Union Find
- Part 2 - Quick Find
- Part 3 - Quick Union
- Part 4 - Improved Quick Union
- Part 5 - Related Interview Questions
Weighted Quick Union
Quick Unionbut avoid tall tree, to avoid traversing through very long path
- Use an extra array to track the size of each tree (stored in the root node)
- Link the smaller tree to the root of the larger tree
- The size of the new tree is the total size of both tree
||Depth of any node x is at most lg
lg= base-2 logarithm
Quick Union with Path Compression
Quick Unionbut try to flatten the tree
- Every time we compute the root of one item (by traversing through the path to the root), set that item to point directly to the root.
- Next time when we call the function to find the root of that same item, we don’t have to traverse through the full path again
For path compression, if the
root is called many times enough, the complexity will become
when the tree become flatten.