# BVL Balanced Tree

I have an issue about proving the next problem:

Let's define a BVL tree, which is a binary tree, who satisfied the feature that the difference between the heights of the children of a node, is at most 2.

Meaning|height(node.left) - height(node.right)| <= 2 Prove that BVL tree is a balanced tree.

Now I do know it's some kind of extension of AVL tree. Well, as we know, the defenition of a balanced tree is related to its height, which is O(logn)

However, trying to perform an induction on N for BVL tree, ends with failure..

Can someong turn on the light and give me a hint?

Thanks!

• You can generalize height balance to arbitrary boundaries; as long as it's constant, the height will be logarithmic. The proof is very similar to the one for AVL trees; just go through and adapt. – Raphael Jul 6 '17 at 19:00

## 1 Answer

If you want to show that the height is $h=\mathcal O(\log(n))$ then I would suggest the following:
Define $n_h$ as the minimum vertices in tree with height $h$
Then to get the minimum vertices for given height:
$n_h = n_{h-1} + n_{h-3}\\ n_h \ge 2n_{h-3}$

Now from the inequality you know that:

$n_{h-3} \ge 2*n_{h-6}$

(Just changing index)

Placing it to the former inequality doing it again and again:

$n_h \ge 2n_{h-3} \ge 2 * (2n_{h-6}) \ge 2 * 2 * (2n_{h-9}) \ge ...\ge 2*2*...*2*c\\$
So lets say that you did 'i' iterations, then $n_h \ge 2^i*c$

$\Rightarrow n_h \ge 2^i*c$
where $c$ is the minimum amount of vertices in the base case and $c \ge 1$
The recursion will stop when the index will be ($0/1/2$):

$\Rightarrow h - 3 - 3i = 0\\ \Rightarrow i = \frac{h-3}{3}\\ \Rightarrow n_h \ge 2^\frac{h-3}{3}\\ 3(1 + \log(n_h)) \ge h\\ \Rightarrow h = \mathcal O(\log(n))$

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Jul 6 '17 at 19:00
• Hi Omer, Thanks for the details!. However, I completely lost it, when u added that i to the inequality, can u explain that ? – StevenU Jul 6 '17 at 19:33
• Hey, i've edited it to explain more deeply how I got this 'i'. – Omer Nizri Jul 7 '17 at 6:42
• Thanks again, it's more clearly now. How did you manage to reach the line h - 3- 3i? – StevenU Jul 9 '17 at 17:27