Why does the weighted quick union algorithm consider the sizes of the tree instead of their heights?

Question

I was watching Robert Sedgewick's video on improvements to quick union. (https://youtu.be/sEo6LlPxpHE?t=267)

There he uses size of the tree rather than the height. Actually the problem is finding the root node . finding will be difficult if the height is high. so we should find a way to mitigate the effect of height. Only if we compare heights will it not work as expected ? will connecting shorter tree to taller tree not solve the problem instead doing :connecting tree with smaller number of nodes to tree with larger number of nodes ?

what about the following case ?

according to the logic in video:

size of A tree = 4

size of B tree = 7

and if you connect A to B . actually we are making the resulting tree taller(height 4). But had we done it based on tree heights we could have solved it by connecting tree B to A . and so the resulting tree will have height 3.

Am I right ? If wrong where am I wrong ?

Answer 1

Keep in mind that most implementations of a disjoint-set forest apply the path compression optimization, in which during every lookup, you change the parent pointers of all the nodes in the chain so that they all point to their representative.

It turns out that if you use path compression and keep track of the heights of all the nodes prior to compressing them, then the asymptotic performance of linking by height (usually called union-by-rank, where the "rank" is the height prior to any compressions) and linking by weight are identical. Both give the inverse Ackermann time complexity. This result comes from this paper, which is highly technical but does prove both results.

Even if you don't do this, though, there's another way to see that these two approaches are (roughly) equal to one another. Notice that if you have a tree of height one, it has to have at least two nodes in it. Why? Well, the only way you can make a tree of height one is to merge to trees of height zero, each of which must have at least one node. Using similar logic, you can see that if you have a tree of height two, then it must have at least four nodes, since to form it you had to merge two trees of height one together. More generally, you can show that a tree of height n must have at least 2ⁿ nodes in it. Therefore, merging by the height is essentially the same as merging by weight, since there's a close connection between the heights and sizes of the trees.

Hope this helps!