Quick union and heuristic by size

Question

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

Answer 1

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$