CODEWITHSUNDEEP
algorithmdata-structurestreetime-complexitydisjoint-sets
user6337930
user6337930

Reputation:

Disjoint Set in a special ways?

We implement Disjoint Data structure with tree. in this data structure makeset() create a set with one element, merge(i, j) merge two tree of set i and j in such a way that tree with lower height become a child of root of the second tree. if we do n makeset() operation and n-1 merge() operations in random manner, and then do one find operation. what is the cost of this find operation in worst case?

I) O(n)
II) O(1)
III) O(n log n)
IV) O(log n)

Answer: IV.

Anyone could mentioned a good tips that the author get this solution?

Upvotes: 0

Views: 239

Answers (1)

Jordi Vermeulen
Jordi Vermeulen

Reputation: 1198

The O(log n) find is only true when you use union by rank (also known as weighted union). When we use this optimisation, we always place the tree with lower rank under the root of the tree with higher rank. If both have the same rank, we choose arbitrarily, but increase the rank of the resulting tree by one. This gives an O(log n) bound on the depth of the tree. We can prove this by showing that a node that is i levels below the root (equivalent to being in a tree of rank >= i) is in a tree of at least 2i nodes (this is the same as showing a tree of size n has log n depth). This is easily done with induction.

Induction hypothesis: tree size is >= 2^j for j < i.
Case i == 0: the node is the root, size is 1 = 2^0.
Case i + 1: the length of a path is i + 1 if it was i and the tree was then placed underneath
            another tree. By the induction hypothesis, it was in a tree of size >= 2^i at
            that time. It is being placed under another tree, which by our merge rules means
            it has at least rank i as well, and therefore also had >= 2^i nodes. The new tree
            therefor has >= 2^i + 2^i = 2^(i + 1) nodes.

Upvotes: 1

Related Questions