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

 

Transcribed Image Text:

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 and the minimum number of vertices in an AVL tree. Find appropriate initial conditions for these difference equations. Solve both these initial value problems and thus obtain bounds on the number of vertices in an AVL tree of height h. (HINT: Thinking of Fibonacci might help. ) 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 and the minimum number of vertices in an AVL tree. Find appropriate initial conditions for these difference equations. Solve both these initial value problems and thus obtain bounds on the number of vertices in an AVL tree of height h. (HINT: Thinking of Fibonacci might help. )