1
$\begingroup$

I'm wondering given a set $A$ of $n$ numbers, is there any procedure that can create a tree of height $lg(n)$ that contain all the elements of $A$ by applying consecutive Union by rank operation in a Union-Find data structure.

The Find operation is naïve and did not use path compression.

The initial state is a forest of singletons with every element of $A$.

All my attempts to do so failed, because at some point there were a tree with a very big rank that all the other tree in the forest got union to him.

I'm not asking about running time like here, but the structure of the tree itself that contain all the elements of $A$.

$\endgroup$

1 Answer 1

2
$\begingroup$

Use the below recursive construction:

constructLogHeightTree($A$)

  • Let $n$ be size of $A$, then:
    • If $n=1$ return
    • Otherwise:
      • Split $A$ into $2$ sets $A_1$ and $A_2$ with $\lceil \frac{n}{2} \rceil$ and $\lfloor \frac{n}{2} \rfloor$ sizes respectively.
      • Call constructLogHeightTree($A_1$) and constructLogHeightTree($A_2$).
      • Take any one element of $A_1$ and any one of $A_2$, and join them using a global union find.
      • Return.

Analysis

I use strong induction to show that using the above procedure, the height of the union-find tree for $n$ elements $h(n)$ will be $\lfloor \log_2 n \rfloor$.

Base step $n=1$

The height $h(1)$ would be $0$ as the tree contains only $1$ node. This shows $h(n) = \lfloor \log_2 n \rfloor = 0$ for $n=1$

Inductive step

Using the induction hypothesis, we can say that the tree produced by

  • constructLogHeightTree($A_1$) will have a height of $h\left( \left\lceil \frac{n}{2} \right\rceil \right) = \left\lfloor \log_2 \left\lceil \frac{n}{2} \right\rceil \right\rfloor$

  • constructLogHeightTree($A_2$) will have a height of $h\left( \left\lfloor \frac{n}{2} \right\rfloor \right) = \left\lfloor \log_2 \left\lfloor \frac{n}{2} \right\rfloor \right\rfloor$

As $\lceil \frac{n}{2} \rceil \ge \lfloor \frac{n}{2} \rfloor$, W.L.O.G. we can say that the root of $A_2$'s tree will get attached to ( or have its parent set to) the root $A_1$'s tree. Then the final height of the tree is $$\begin{split} h(n) &= \max\left( h\left( \left\lceil \frac{n}{2} \right\rceil \right) , h\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + 1 \right) \\ &= \max\left( \left\lfloor \log_2 \left\lceil \frac{n}{2} \right\rceil \right\rfloor, \left\lfloor \log_2 \left\lfloor \frac{n}{2} \right\rfloor \right\rfloor + 1 \right) \\ &= \left\lfloor \log_2 \left\lfloor \frac{n}{2} \right\rfloor \right\rfloor + 1 \\ &= \left\lfloor \log_2 \cdot \left\lfloor \frac{n}{2} \right\rfloor + 1 \right\rfloor \\ &= \left\lfloor \log_2 \left( 2 \cdot \left\lfloor \frac{n}{2} \right\rfloor \right) \right\rfloor \\ &= \left\lfloor \log_2 n \right\rfloor \\ \end{split}$$

$\endgroup$
6
  • $\begingroup$ Thank you! I tried to run the procedure for $A=\left \{ 1,...,9 \right \}$ and I got the following tree: root = 3, children of 3 = 4,5,1,6 , children of 1 = 2, children of 6 = 7,8, children of 8 = 9. Will you be able to confirm this ? Also, in order to determine the time complexity of the the procedure, one should solve $T(n)=2T(\frac{n}{2})+O(lg\ n)$ ? $\endgroup$
    – Daniel
    Commented Jun 22 at 16:19
  • $\begingroup$ I'm also falling to understand why the height of the tree will be Θ(lg n). Will you able to elaborate a little more on this ? $\endgroup$
    – Daniel
    Commented Jun 22 at 16:22
  • $\begingroup$ @Daniel For your example test case, not necessarily. When I say split $A$ into $A_1$ and $A_2$, I don't necessarily say split by the middle. You can split however you want and end up with a different tree altogether. It also depends on how you implement union find ( what do you do when the sizes of sets are equal). The only thing you can say for sure is the height $\ge \lfloor \log_2 n \rfloor = 3$ $\endgroup$
    – EnEm
    Commented Jun 22 at 17:46
  • $\begingroup$ @Daniel Secondly, you don't have to analyse the time complexity of this method, because it is only used for analysis. Even if the complexity was, let's say, $\mathcal{O}((n!)^{n!})$, we can still use it to prove that union find height is $\Omega(\log n)$. If you want to know the complexity anyways for fun, It would be what you have written yes. $\endgroup$
    – EnEm
    Commented Jun 22 at 17:50
  • $\begingroup$ @Daniel Added some detailed explanation to your 3rd question now $\endgroup$
    – EnEm
    Commented Jun 22 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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