2
$\begingroup$

Let T be an AVL tree of height 3. What is the smallest number of entries it can store? Note that a tree with one node (only the root) has the height of zero and stores one element.


The only method I could think of was just drawing an AVL tree and trying to minimize the number of nodes in which I get an answer of 7. enter image description here But this method is prone to error in my opinion and I'm not even sure if my answer is correct. So is there any method or equation to solve this without having to graph it?

$\endgroup$
2
$\begingroup$

Prove a lower bound of 7 vertices:

Since the tree is of height 3, it must have a path of length 3 from the root to a leaf, so we already have to have 4 vertices; $r-v_1-v_2-v_3$. Now r has to have balance factor in $\{1,0,-1\}$ (i.e. $|\text{BF}(r)|\leq1$) so it must have a path of length at least two on it's other subtree, so we have $r-v_4-v_5$ (at least two more vertices).

For the same reasons (BF) $v_1$ has to have at least one child on it's other subtree, so we have $v_1-v_6$ (at least one more vertex).

So we have proved that an AVL tree of height 3 has to have at least 7 vertices, your example shows that there is an AVL tree with 7 vertices, so the minimum is 7.

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