3.Quick-Union
Data Structure
- Integer array id[] of Size N
- id[i] is parent of i (value is parent, index is item)
- root of i is id[id[i]]...
- root: id[i] = i
Find
- Check if p and q have the same root ( id[i] = i)
Union
- set the id of p's root to the id of q's root (only need to change one value in the array)
Cons
- tree can be tall
- Find is too expensive.
4. Improvement
Weighted quick-union
- Avoid tall trees
- keep track of the size of each tree (number of objects)
- link root of the smaller tree to root of the larger tree
Data structure
- Same as quick-union, but maintain extra array to count the number of objects in each tree
Find
Union
- link root of the smaller tree to root of the larger tree
- update the count array
Quick-union with Path compression
- After getting the root of p, set the id of each examined node to the point to that root
- make every other node in the path point to its grandparent