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.

Improve this question
$\endgroup$
3
  • $\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, 2019 at 13:32
  • $\begingroup$ Yes Steven. Exactly. We need to prove that this family is height balanced. $\endgroup$
    – Neo182
    Jun 4, 2019 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, 2019 at 21:40

3 Answers 3

Reset to default
4
$\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)$.

Improve this answer
$\endgroup$
2
  • $\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, 2019 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, 2019 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|)$.

Improve this answer
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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