5. An AVL tree is a binary tree in which at each vertex the heights of the right

Question

5. An AVL tree is a binary tree in which at each vertex the heights of the right and left subtrees of that vertex differ by at most 1 If the AVL tree is of height h what is the maximum possible number of vertices in the tree What is the minimum number of vertices! Derive difference equations for the maximum minimum number of vertices in an AVL tree. Find appropriate initial conditions for these difference Solve both these initial value problems and thus obtain bounds on the number of vertices in an AVL tree of height h. equations. HINT : Thinking of Fibonacci might help.)

Explanation / Answer

5)

the maximum possible vertices at height h in avl tree:

at height h = 0

Max number of nodes = 1

--------------------------

at height h = 1

Max number of nodes = 3

--------------------------

at height h = 2

Max number of nodes = 7

--------------------------

at height h = 3

Max number of nodes = 15

--------------------------

so...at height : h

Max number of nodes = 2^h+1-1

lets check it

h =2

2^2+1-1 = 2^3-1 = 8-1 = 7

the manimum possible vertices at height h in avl tree:

at height h = 0

min number of nodes = 1

--------------------------

at height h = 1

Min number of nodes = 2

--------------------------

at height h = 2

Min number of nodes = 4

--------------------------

at height h = 3

Min number of nodes = 7 = 4+2+1

--------------------------

so...at height : h

Max number of nodes = Numberofnodes(h) = Numberofnodes(h-1)+Numberofnodes(h-2)

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.