Union/find algorithm without union by rank for disjoint-set forests data structure?

I googled for "without union by rank" and the second link that came up was this one.

I googled for "without union by rank" and the second link that came up was this one: ...We close this section with an analysis of union–find with path compression but without union by rank... The union-find datastructure with path compression but without union by rank processes m find and n-1 link operations in time O((m+n) log n).

That is a great find! I admit that I didn't Google it first because I didn't think anyone would've thought of addressing it. This means that the amortized cost per operation IS O(log n), and without the additional cost in space to keep track of the rank!

– polygenelubricants Feb 24 '10 at 14:41.

Path compression flattens the tree structure. Union by rank helps to merge. Assume that you skip the latter.So now, you have a forest with no rank information to choose how to merge.

Potentially, you now run the risk of merging a tree with a larger depth to one with a smaller depth -- leading to an unbalanced tree structure. In the worst case, you may end up with a linked list. Your Union's amortized time complexity increases even if that for Find remains the same.

IMO, It'd be better to skip path compression but not rank.

I agree with what you said, but it would help if someone can do the rigorous analysis to show what the performance is with path compression but not union by rank. Unfortunately I'm not familiar with the techniques involved to do such analysis. I have no clue how inverse Ackermann function play a role in the complete implementation, for example.

– polygenelubricants Feb 24 '10 at 3:24.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.