Union Find - Why we are checking Size for Weighted Quick Union

Question

I was going through Princeton's Algorithms course on Coursera.

In the Union find section, for Weighted Quick union, we merge trees depending upon which tree is smaller in terms of Size.

However, I don't understand that why are we using Size rather than Depth to decide which tree is larger and which is smaller.

Wouldn't the Worst case time complexity of finding root increase because of tree Depth?

In the above example, if we merge the 2 trees by checking size, the depth of resulting tree is 4 whereas on checking by depth we get a smaller resulting tree depth.

Answer 1

It's very common to use "rank" instead of size for the weighting. Height is not used, because the height of a tree can be changed by path compression in ways that are difficult to track. The rank of a tree is what the height would be if path compression wasn't in use.

Using the size of the tree, however, works just as well as rank -- the worst case complexities of union and find remain the same -- and is just as easy to track. Furthermore, the size of each set can be a useful thing to know! For that reason, I prefer weighting by size instead of rank.