# Bounding the height of a tree in a variant of disjoint set union

Consider a variant of link-by-size implementation of the Union–Find data structure, in which trees will be linked by the logarithm of the size. Let $$\ell_i$$ = $$⌊\log_2|T_i|⌋$$ and, when merging $$T_i$$ and $$T_j$$, we use the following rules:

• if $$\ell_i$$ < $$\ell_j$$ , we make the root of $$T_i$$ point to the root of $$T_j$$ ;

• if $$\ell_i$$ > $$\ell_j$$ , we make the root of $$T_j$$ point to the root of $$T_i$$;

• if $$\ell_i$$ = $$\ell_j$$ , we choose one of the two options above arbitrarily.

Recall that we define the height of a rooted tree as the length of the longest path from a leaf to the root; e.g., the height of a tree that only contains one node is $$0$$. Prove that under our rules, the height of a tree that contains $$s$$ nodes does not exceed $$2\log_2s$$.

I think this is meant to be solved using induction - I've solved the $$\ell_i>\ell_j$$ case (the $$\ell_j$$>$$\ell_i$$ is symmetric).

I'm stuck on the $$\ell_i$$ = $$\ell_j$$ case, here's my attempt:

$$\ell_i \le \log_2|T_i|$$
$$\implies 2^{\ell_i} \le |T_i|$$

as $$\ell_i = \ell_j$$ we have $$2^{\ell_i} = 2^{\ell_j}$$

$$\therefore 2\log_2(|T_i|+|T_j|) \ge 2\log_2(2^{\ell_i} + 2^{\ell_j})$$
$$= 2\log_2(2\cdot2^{\ell_i})$$
$$= 2\log_2(2^{\ell_i + 1})$$

(which should be but I can't prove)$$> h + 1$$ where $$h$$ is the height of $$T_i$$

How do I prove this?

Let me solve the case where you got stuck. Suppose $$T_i$$ with $$\ell_i$$ and $$T_j$$ with $$\ell_j$$ is merged into tree $$T$$, where $$\ell_i$$ = $$\ell_j$$.

WLOG, suppose we make the root of $$T_i$$ point to the root of $$T_j$$. Then $$h(T)$$ is either $$1+h(T_i)$$ or $$h(T_j)$$.

$$|T| = |T_i| + |T_j|\ge|T_i| + 2^{\ell_j}=|T_i| + 2^{\ell_i+1}/2\gt|T_i| + |T_i|/2=\frac32|T_i|$$

Let $$\log$$ mean logarithm with base 2. Then $$2\log|T|\gt 2\log(\frac32|T_i|)=\log\frac94+2\log|T_i|\gt1+2\log|T_i|$$

Thanks to the induction hypothesis,

• $$1+h(T_i)\le1+2\log|T_i|\lt 2\log|T|$$
• $$h(T_j)\le 2\log|T_j|\lt 2\log|T|$$.

We conclude $$h(T)\lt 2\log|T|$$. Other cases can be done, in fact, more or less similarly.