CODEWITHSUNDEEP
algorithmdata-structuresunion-find
ALLAN
ALLAN

Reputation: 71

Will applying Path compression to Union Find always results in a flat tree, If so, Why?

The below images show a Union find Problem solved by rank with path compression. If you don't understand my handwriting then read the description below to understand what I have done.

Description:

First I have done Union of 1 and 2. Second, Union(3,4). Third Union(5,6) and so on by comparing their ranks while also doing path compression when finding the representative element of the tree whose union is to be done.

My Doubt:

My doubt is, If you look at the final tree in the image, you'll see a tree completely flat ( flat means I meant the tree's depth ). Will path compression always result in a flat tree no matter how many elements are present? And Also how can we find the Union_find's time complexity with path compression?

enter image description here

enter image description here

Upvotes: 1

Views: 320

Answers (1)

comingstorm
comingstorm

Reputation: 26117

It is possible to build inverse-trees of unlimited depth. E.g., if you happen to always choose the roots as your Union() arguments, then no paths will be compressed, and you can build your tree as tall as you like.

If (as your written notes suggest) you use rank to choose the root resulting from your union, then your trees will be balanced, so you will need Ω(2^n) operations to generate a tree of depth n. (Specifically: to build a tree of of depth n, first build two trees of depth n-1 and take the Union() of their roots.)

The amortized time complexity of union-find with rank-matching and path compression is known to be O(inverse_ackermann).

Upvotes: 2

Related Questions