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

Question

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?

Answer 1

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.