Finding the minimum "internal" nodes of AVL tree?

user_13915008 0
Viewed 346

I know how to find the minimum numbers of nodes in an AVL tree of height h (which includes external nodes) with the formula n(h) = n(h-1) + n(h-2) + 1 but I was wondering if there was a formula to just find the minimum internal nodes only of an AVL tree with height h.

So for n(3) = 4, if we're only counting internal nodes. n(4) = 7, if we're only counting internal nodes. I can draw it out and count the internal nodes but when you get to bigger AVL trees it's a mess.

I can't seem to find anything on this and trying to find a pattern with consistent answers has only led to hours of frustration. Thanks in advance.

avl-tree binary-tree data-structures
1 Answers

Yep, there’s a nice way to calculate this. Let’s begin with the two simplest AVL trees, which have order 0 and order 1:

*    *
     |
     *

This first tree has no internal nodes, and the second has one internal node. This gives us our base cases for a recurrence relation:

  • I(0) = 0
  • I(1) = 1

From here, we notice that the way to get the fewest internal nodes in an AVL tree of order n+2 is to pick two trees of order n and n+1 as children (minimizing the number of nodes) that have the fewest internal nodes possible. The resulting tree will have a number of internal nodes equal to the number of internal nodes in the two subtrees, plus one for the new root. This means that

  • I(n+2) = I(n) + I(n+1) + 1.

Applying this recurrence gives us the sequence

0, 1, 2, 4, 7, 12, 20, etc.

And hey - have we seen this before somewhere? We have! Adding one to each term gives us

1, 2, 3, 5, 8, 13, 21, etc.

which is the Fibonacci sequence, shifted down two positions! So our hypothesis is that

I(n) = F(n+2) - 1

You can prove that this is the case by induction on n.

Here’s a different way to arrive at this result. Imagine you take an AVL tree of height n and remove all the leaves. You’re now left with an AVL tree of height n-1 (prove this!), and all of the remaining nodes in this tree are the internal nodes of the original tree. The smallest possible number of nodes in an AVL tree of height n is F(n+2)-1, matching our result.

user_5015570
Related