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 xx is at most lg⁡N\lg N.

Exercise To justify the proposition, complete the following statements by filling in the blanks.

  • The depth of xx increases at most by ______ when tree T1T_1 containing xx merges into another tree T2T_2.
  • Since the larger tree (among T1T_1 and T2T_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 xx can _______ at most ________ times because if you start with one node and _______________ you will get NN, and there is only NN nodes in the tree.
Solution
  • The depth of xx increases at most by one when tree T1T_1 containing xx merges into another tree T2T_2.
    • (Assume the worst case where each tree has mm elements and a height of mm. Then the resulting tree after union will have 2m2m elements and heigh of m+1m+1.)
  • Since the larger tree (among T1T_1 and T2T_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 xx can double at most lg⁡N\lg N times because if you start with one node and double it lg⁡N\lg N times you will get NN, and there is only NN nodes in the tree.

From the proposition, it follows the height of the tree is in O(lg⁡N)\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.