2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.