3
$\begingroup$

Studying Quick-Find and Quick-Union heuristic I've found clear that:

  • with quick find trees and a union based on the size of the trees we can make a union in $T_{am}(n)=O(\log(n))$

  • with quick find trees and a union based on the height of the trees we can make a find in $T(n)=O(\log(n))$

But I read that using quick union trees and an union based on the size of the trees we can also have a find in $T(n)=O(\log(n))$, so my question is how can this be demonstrated? What relationship is there between height and size?

For example knowing that $\text{size}(A)=4$ I could have both:

        A                A
      / | \              |
     1  2  3             1
                         |
                         2
                         |
                         3
$\endgroup$
  • $\begingroup$ Union by rank is the same as union by size! You make the root of the tree with fewer nodes a child of the root of the tree with more nodes. Do you want to say union by height? $\endgroup$ – saadtaame Feb 10 '13 at 15:30
  • $\begingroup$ yes you're right, I mean union by height, I've edited. $\endgroup$ – abc Feb 10 '13 at 16:37
1
$\begingroup$

To union-by-size two trees, you have to find their roots first. Since union-by-size takes logarithmic time (your first bullet), then first must take logarithmic time as well.

Here is a more formal argument. Say you want to union-by-size two trees $T_1$ and $T_2$. Assume that their heights are logarithmic in their sizes:

$H(T_1)\le \log(n_1)$ and $H(T_2)\le \log(n_2)$

Where $H$ is the height function and $n_1$ (resp. $n_2$) is the number of nodes in tree $T_1$ (resp. tree $T_2$). There are two cases to consider: either one tree has fewer nodes than the other or both trees have the same number of nodes.

Case # 1

Say $n_1\lt n_2$. The resulting tree $T$ has height $H(T)=\max\{H(T_1)+1, H(T_2)\}$

Depending on the max we have:

$H(T)\le \log(n_1) + 1\le \log(2n_1)\le \log(n_1 + n_2)\le \log(n)$ (because $n_1\lt n_2$)

Or,

$H(T)\le \log(n_2)\le \log(n)$

Case # 2

In this case, $H(T)\le \max\{H(T_1),H(T_2)\}+1$.

Again depending on the max we have:

$H(T)\le \log(n_1)+1\le \log(2n_1)\le \log(n_1+n_2)\le \log(n)$ (because $n_1=n_2$) and likewise for the other one.

For the base case choose $n=1$ because $H(T)=0\le \log(1)=0$

$\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.