2
$\begingroup$

A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( \log n)$.

Given a family of trees such that for every tree $t$ in the family, for every node $v$ in $t$, the height difference between the right subtree of $v$ and the left subtree of $v$ is at most $c$, where $c$ is some constant.

I understand this claim is true. It is the general case for AVL trees. I just don't know how to prove it formally.

$\endgroup$
  • $\begingroup$ What is the claim you're trying to prove? Do you want to show that such a family is height balanced? $\endgroup$ – Steven Jun 4 at 13:32
  • $\begingroup$ Yes Steven. Exactly. We need to prove that this family is height balanced. $\endgroup$ – Neo182 Jun 4 at 13:33
  • $\begingroup$ Is this an infinite family? Big-O notation applies to asymptotic behavior, which doesn't apply to finite cases. $\endgroup$ – Acccumulation Jun 4 at 21:40
3
$\begingroup$

Let us denote by $N_h$ the minimum number of leaves of a tree in your family of height $h$. Clearly $N_0 = 1$, and $$ N_h = N_{h-1} + \min_{0 \leq d \leq c} N_{h-1-d}. $$ (Here $N_h = 0$ if $h < 0$.) You can prove inductively that $N_h$ is monotone, and so for $h \geq c+1$, $$ N_h = N_{h-1} + N_{h-1-c}. $$ This is a recurrence relation whose solution is $N_h = \Theta(\alpha^h)$, where $\alpha$ is the maximal real root of $x^{c+1} - x^c - 1= 0$; for example, when $c = 1$, $x$ is the golden ratio.

Since the number of leaves in a tree of height $h$ is $\Omega(\alpha^h)$, it follows that a tree containing $n$ leaves has height $O(\log n)$.

$\endgroup$
  • $\begingroup$ Hey Yuval. Thank you. I have few questions: 1. Why we want to show that Nh is monotone? And to show that I need to prove that Nh+1 >= Nh? 2. How do I reach the expression a^h? $\endgroup$ – Neo182 Jun 4 at 16:06
  • $\begingroup$ We want to show that $N_h$ is monotone so we could get a simpler recurrence relation for it. We can then solve it using classical techniques to get the answer $\Theta(\alpha^h)$. See for example Wikipedia. $\endgroup$ – Yuval Filmus Jun 4 at 16:18
1
$\begingroup$

Let $T_h$ be any tree that satisfies your property and has height at least $h$. Let $|T_h|$ be the number of its nodes.

For $0 \le h \le c$, $|T_h| \ge 1$. For $h > c \cdot i$, with $i \in \mathbb{N}^+$, you have: $$ |T_h| \ge 1 + | T_{c \cdot i} | + | T_{ c \cdot (i-1)}| \ge 2 | T'_{ c \cdot (i-1)}|, $$ where $T_{c \cdot i}$, $T_{ c \cdot (i-1)}$, and $T'_{ c \cdot (i-1)}$ are trees of height at least $c \cdot i$, $ c \cdot (i-1)$, and $ c \cdot (i-1)$, respectively, that also satisfy your property.

Let $T$ be a tree of height $H$ from your family. From the above observations (choosing $h=H$) it follows that $|T| \ge 2^{\left\lfloor \frac{H}{c+1} \right\rfloor} \ge 2^{\frac{H}{c+1} - 1}$, or equivalently, $H \le (c+1)( 1+ \log |T|) = O(\log |T|)$.

$\endgroup$
0
$\begingroup$

Thanks everyone for the answers. Finally I decided to take the proof of AVL tree has a height of O (log n ) and implenent the recurrence with the constant c. Basically Avl is a special case of this claim so taking the proof of AVL using the same idea led me to the proof. Instead of N(h) = N (h-1) + N (h-2) + 1 I used N(h) = N ( h -1) + N ( h - 1 - c) + 1

$\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.