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
Quick union and heuristic by size
algorithms;heuristics;union find
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 # 1Say $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 # 2In 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$