search
Log In
17 votes
2.2k 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$?
in DS
edited by
2.2k views
2

Min nodes recurrence relation when height $'h'$ is given: 

$T(h)=T(h-1)+T(h-2)+1$

Max nodes recurrence relation when height $'h'$ is given: 

$T(h)=2T(h-1)+1$

1 Answer

30 votes
 
Best answer
  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:
    $\mathbf{N(h) = N(h-1) + N(h-2) + 1}$
     
  2. This recursion can be graphically seen as below:

Using the above recursion, we need to find $N(8)$
$N(0) = 1$
$N(1) = 2$
$N(2) = N(1) + N(0) + 1 = 1 + 2 + 1 = 4$
$N(3) = N(2) + N(1) + 1 = 2 + 4 + 1 = 7$
$N(4) = N(3) + N(2) + 1 = 4 + 7 + 1 = 12$
$N(5) = N(4) + N(3) + 1 = 7 + 12 + 1 = 20$
$N(6) = N(5) + N(4) + 1 = 12 + 20 + 1 = 33$
$N(7) = N(6) + N(5) + 1 = 20 + 33 + 1 = 54$
$N(8) = N(7) + N(6) + 1 = 33 + 54 + 1 = 88$

So, answer for (b) is $88$.


edited by
0
How to solve this recurrence relation :-

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

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

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

0


Archive of URL provided by sachin

@sachin

I think $n(1) = 2$ and $n(2) = 4$.

Related questions

23 votes
8 answers
1
6.3k views
A complete $n$-ary tree is one in which every node has $0$ or $n$ sons. If $x$ is the number of internal nodes of a complete $n$-ary tree, the number of leaves in it is given by $x(n-1) +1$ $xn-1$ $xn +1$ $x(n+1)$
asked Sep 26, 2014 in DS Kathleen 6.3k views
27 votes
6 answers
2
6.6k views
Which of the following statements is false? A tree with a $n$ nodes has $(n – 1)$ edges A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results. A complete binary tree with $n$ internal nodes has $(n + 1)$ leaves. The maximum number of nodes in a binary tree of height h is $2^{h+1} - 1$
asked Sep 26, 2014 in DS Kathleen 6.6k views
18 votes
1 answer
3
1.8k views
Draw the binary tree with node labels $\text{a, b, c, d, e, f and g}$ for which the inorder and postorder traversals result in the following sequences: Inorder: $\text{a f b c d g e}$ Postorder: $\text{a f c g e d b}$
asked Sep 26, 2014 in DS Kathleen 1.8k views
18 votes
5 answers
4
3.3k views
Let $p$ be a pointer as shown in the figure in a single linked list. What do the following assignment statements achieve? q: = p -> next p -> next:= q -> next q -> next:=(q -> next) -> next (p -> next) -> next:= q
asked Sep 26, 2014 in DS Kathleen 3.3k views
...