1.1k views
1. Derive a recurrence relation for the size of the smallest AVL tree with height $h$.
2. What is the size of the smallest AVL tree with height $8$?
edited | 1.1k views

1. Consider a function $N(h)$ which represents the smallest number of nodes $n$ for an AVL tree with height $h$ and satisfies $n = N(h)$.
For $h=0$ we have, number of nodes $= 1$. So $N(0) = 1$
For $h = 1$, we have, number of nodes $= 2$. We could take $3$, but we require the smallest graph (a graph with smallest number of nodes) so we take $2$. It means that to create a tree with height $14 we need at least$24$nodes. So$N(1) = 2$Now, for$h = 2$, we need to create a node with a child subtree of height$1$. This may be the right or left subtree. But since this is an AVL tree, to balance a child subtree of height let's say$Hs$, we need the other child to have a height of$Hs-1$,$Hs$or$Hs+1$. But we take$Hs-1$for minimal case. In simple words, a node with height$5$must have a child with height$4 (Hs)$and another child with height$3 (Hs-1)$. So$N(2)$can be obtained as:$N(2) = N(1) + (0) + 1$($1$is added to count the parent node,$N(1)$or$N(Hs)$and$N(0)$or$N(Hs-1)$represent two subtrees.) Similarly:$N(3) = N(2) + N(1) + 1$and generalizing:$\mathsf{N(h) = N(h-1) + N(h-2) + 1}$This recursion can be graphically seen as below: 2. Using the above recursion, we need to find$N(8)N(0) = 1N(1) = 2N(2) = N(1) + N(0) + 1 = 1 + 2 + 1 = 4N(3) = N(2) + N(1) + 1 = 2 + 4 + 1 = 7N(4) = N(3) + N(2) + 1 = 4 + 7 + 1 = 12N(5) = N(4) + N(3) + 1 = 7 + 12 + 1 = 20N(6) = N(5) + N(4) + 1 = 12 + 20 + 1 = 33N(7) = N(6) + N(5) + 1 = 20 + 33 + 1 = 54N(8) = N(7) + N(6) + 1 = 33 + 54 + 1 = 88$So, answer for b) is$88\$.

edited
0
How to solve this recurrence relation :-

N(h) = N(h - 1) + 1 + N(h - 2) ; h > 0

N(h) = 1 ; h = 0
+2
using linear nonhomogeneous recurrence relation with constant coefficent method, you can read from rosen
+5

In order to put the minimum number of nodes in an AVL tree of height h, we must:

• put the minimum number of nodes in its 2 sub trees

Because the maximum difference in height is 1 (one), the minimum sub trees are as follows:

• One of the sub tree has height h−1 (in order to make the height of the original tree = h)
• The other sub tree has height h−2 (to minimize the # nodes in the AVL tree)

Both sub trees have the minimum number of nodes

Therefore:

• Sub tree 1 has n(h−1) nodes
• Sub tree 2 has n(h−2) nodes

Relationship between n(h), n(h−1) and n(h−2):

n(h) = 1 + n(h−1) + n(h−2)
n(1) = 1
n(2) = 2

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-height.html