BVL Balanced Tree

Question

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!

Answer 1

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))$