Improvement 1: Weighting

Modify quick-union to avoid tall trees:

  • Keep track of size of each component.
  • Balance by linking small tree below large one.

Exercise Complete the following statements by filling in the blank.

  • Since the larger tree is at least ___________ the smaller tree, the resultant tree (after union) must have at least _________ the number of elements in the smaller one.
  • But there are only $N$ elements, so the union operations can happen at most _________ times.
  • Each union operation increases the height of the resultant tree by at most ______.
  • Thus, the maximum height of the tree is in ____________.
Solution
  • Since the larger tree 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.
  • But there are only $N$ elements, so the union operations (doubling) can happen at most $(\lg N)$ times.
  • Each union operation increases the height of the resultant tree by at most one.
    • Assume the worst case where each tree has $m$ elements, and height of $m$. Then the resulting tree after union will have $2m$ elements and heigh of $m+1$.
  • Thus, the maximum height of the tree is in $O(\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 smaller "rank" to the root of the tree having 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.