Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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
share|improve this question
    
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? –  saadtaame Feb 10 '13 at 15:30
    
yes you're right, I mean union by height, I've edited. –  newbie Feb 10 '13 at 16:37
add comment

1 Answer

up vote 1 down vote accepted

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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