Problem Detail: 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

Asked By : newbie

Answered By : saadtaame

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_1lt 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) + 1le log(2n_1)le log(n_1 + n_2)le log(n)$ (because $n_1lt 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)+1le 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)=0le log(1)=0$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9618 Ask a Question Download Related Notes/Documents