Improvement 1: Weighting
- Trace the Quick Union implementation with a union-by-size heuristic.
- Explain the runtime improvements gained by using the heuristic for union-find operations.
Modify quick-union to avoid tall trees:
- Keep track of the size of each component.
- Balance by linking small tree below large one.
Proposition: In this scheme, the depth of any node $x$ is at most $\lg N$.
Exercise To justify the proposition, complete the following statements by filling in the blanks.
- The depth of $x$ increases at most by
______when tree $T_1$ containing $x$ merges into another tree $T_2$. - Since the larger tree (among $T_1$ and $T_2$) is at least
___________the smaller tree, the resultant tree (after union) must have at least_________the number of elements in the smaller one. - The size of tree containing $x$ can
_______at most________times because if you start with one node and_______________you will get $N$, and there is only $N$ nodes in the tree.
Solution
- The depth of $x$ increases at most by one when tree $T_1$ containing $x$ merges into another tree $T_2$.
- (Assume the worst case where each tree has $m$ elements and a height of $m$. Then the resulting tree after union will have $2m$ elements and heigh of $m+1$.)
- Since the larger tree (among $T_1$ and $T_2$) is at least as large as the smaller tree, the resultant tree (after union) must have at least double the number of elements in the smaller one.
- The size of tree containing $x$ can double at most $\lg N$ times because if you start with one node and double it $\lg N$ times you will get $N$, and there is only $N$ nodes in the tree.
From the proposition, it follows the height of the tree is in $\Omicron(\lg N)$.
The heuristic described above is known as union by size.
Aside: An alternative strategy is union by rank, which always attaches the tree with a smaller "rank" to the root of the tree having a higher rank. The rank of a node is the height of its subtree; the rank of a node can only change if it is a root.