0
$\begingroup$

I implement my data sets with a tree data-structure.

The tree data-structure has a method named MakeSet which creates a set with one node. The tree data-structure has also a method named Merge(i,j) which merges trees of set i and set j in this way: the set with smaller depth becomes a child of the root of the set with larger depth.

I do MakeSet $n$ times and I do MergeSet $n-1$ times with a random order. Then I do a Find operation. What is the cost of Find in a worst case scenario?


I feel like the answer might be $O(n\log{n})$, because after doing $n$ MakeSet and $n-1$ MergeSet, it might be safe to say that we have a tree with $n$ nodes and height of $\log{n}$. I'm not sure.

$\endgroup$
1
$\begingroup$

Since my two comments already form the solution, I can also write the answer in total.

If you have a datastructure consisting of a bunch of trees, then the worst-case cost of a Find-Operation is the maximal height of a tree in your data structure. Your trees are built from $n$ trees consisting of a single node each by $n-1$ Merge-Operations. A Merge-Operation merges two trees such that the tree of smaller height is added to the root of the tree of larger height.

First observation: If you merge two trees of different height, then the resulting tree has the same height as the initial tree of larger height.

Second observation: If you merge two trees of the same height $h$, then the resultung tree has height $h+1$.

Conclusion: To increase the maximum height from $h$ to $h+1$, you first need two trees of height $h$.
So the worst-case scenario in your setting is the following: You initially merge two trees consisting of a single node each. This gives a tree of height $1$. You now need to merge two other trees consisting of a single node each such that a second tree of height $1$ occurs. If you now merge this trees of height $1$, then you have a resulting tree of height $2$. Now if you want to increase the height again, you need again $4$ of the initial trees to construct an other tree of height $2$.

The iteration of that argument shows that you can only increase the height $\log n$ times, where $n$ is the number of initial trees.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.