I was studying disjoint set data structure. I studied path compression and union by rank. Initially all the elements are single in their own set and by performing unions we can combine different sets. Now since we are performing union by rank the height of the resultant tree is always minimum. At this point i think that we might not need path compression at all. Am i right? If i am wrong please explain me with an example.
Now since we are performing union by rank the height of the resultant tree is always minimum
If you are union by rank two trees of height h then you get a tree of height h + 1. So you have two trees of height 1 you get tree of height 2. Then if you get another tree of height 2 you might end up combining them into a tree of height 3 and so on. This can give you a very tall tree.
I read is a long time ago and I don't have CLRS handy but I afaik neither of the heuristics by itself is enough to guarantee the best complexity (Akerman stuff). We need them both. But in practice maybe its okay to use just one.