1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Jul 6 '17 at 19:00
3
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Raphael Jul 6 '17 at 19:00
  • $\begingroup$ Hi Omer, Thanks for the details!. However, I completely lost it, when u added that i to the inequality, can u explain that ? $\endgroup$ – StevenU Jul 6 '17 at 19:33
  • $\begingroup$ Hey, i've edited it to explain more deeply how I got this 'i'. $\endgroup$ – Omer Nizri Jul 7 '17 at 6:42
  • $\begingroup$ Thanks again, it's more clearly now. How did you manage to reach the line h - 3- 3i? $\endgroup$ – StevenU Jul 9 '17 at 17:27

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.