4 Quick-Union with Union-by-Rank (10 marks) In class, we saw the Weighted Quick-Union algorithm, which performs UNION in the following way: make the root of the tree containing less elements the child of the root of the tree containing more elements (with ties resolved arbitrarily). Let's call this version of UNION "Union-by-Weight" We will now look at a similar algorithm, which instead uses a version of UNION we will call "Union-by-Rank". Union-by-Rank proceeds via two cases: 1. Suppose we are taking the union of two trees Ti and T2 with heights h and h2 respectively, with hi h2. Then the root of T2 becomes a child of the root of T. In this case, the resulting tree has height equal to the height of Ti 2. If the two trees have the same height, the root of one of the trees becomes a child of the root of the other tree. In this case, the resulting tree has height one greater than each of the original trees. Let n be the number of vertices. Prove that when using Quick-Union with Union-by Rank, a call to CONNECTED takes time O(log n) in the worst case. 4 Quick-Union with Union-by-Rank (10 marks) In class, we saw the Weighted Quick-Union algorithm, which performs UNION in the following way: make the root of the tree containing less elements the child of the root of the tree containing more elements (with ties resolved arbitrarily). Let's call this version of UNION "Union-by-Weight" We will now look at a similar algorithm, which instead uses a version of UNION we will call "Union-by-Rank". Union-by-Rank proceeds via two cases: 1. Suppose we are taking the union of two trees Ti and T2 with heights h and h2 respectively, with hi h2. Then the root of T2 becomes a child of the root of T. In this case, the resulting tree has height equal to the height of Ti 2. If the two trees have the same height, the root of one of the trees becomes a child of the root of the other tree. In this case, the resulting tree has height one greater than each of the original trees. Let n be the number of vertices. Prove that when using Quick-Union with Union-by Rank, a call to CONNECTED takes time O(log n) in the worst case