2
$\begingroup$

Let $α \in [0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by $|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We say that $T$ is $α$-good if, for every node $x$ in the tree with children $y$ and $z$, it holds that $|y|$$|z|$$α|x|$. Show that an $α$-good tree with n nodes has height $O(\log n)$.

I tried using induction for this but made no progress.

Some other observations I made:

$|x| = |y| + |z| + 1$
$\le 2|z| - (|z| - |y|) + 1 $ (WLOG assume $|y|\le|z|$)
$\le 2|z| - ||z| - |y||+1$
$\le 2|z| - \alpha |x| + 1$
$ = 2|z| - \alpha |y| - \alpha |z| + (1 - \alpha)$

I'm not sure if it helps.

$\endgroup$
0

2 Answers 2

6
$\begingroup$

$$2|y| = (|y|-|z|) + (|y|+|z|)\le \alpha |x| + |x| - 1.$$ So, $|x| \ge \frac2{1+\alpha}|y|$.

Since $y$ is an arbitrary child of $x$, if node $x$ is of height $k$, $|x| \ge \left(\frac2{1+\alpha}\right)^k$.

If an $α$-good tree with $n$ nodes has height $h$, then $$n\ge \left(\frac2{1+\alpha}\right)^h$$

That is, $h\le\log_{\frac2{1+\alpha}}n$, which means $h=O(\log n)$ since $\frac2{1+\alpha}\gt1$.

$\endgroup$
1
  • 1
    $\begingroup$ Damn, you beat me! $\endgroup$
    – Nathaniel
    May 11 at 21:07
5
$\begingroup$

First, note that if $T$ is an $\alpha$-good tree, then for any node $x$ with children $y$ and $z$, without loss of generality, $|y| \leqslant |z| <\frac{1+\alpha}2 |x|$.

Now consider $h_n$ the maximal height of an $\alpha$-good tree of size $\leqslant n$. It is clear that $h_1 = 0$ (or $1$, depending on your definition of height). The property above shows that for $n\geqslant 2$, $h_n \leqslant 1 + h_{\left\lfloor\frac{1+\alpha}2n\right\rfloor}$.

An induction can now show that $h_n \leqslant \log_{\beta}(n)$, with $\beta = \frac2{1+\alpha}$. Since $\alpha < 1$, this is clearly in $\mathcal{O}(\log n)$.

$\endgroup$

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.