an AVL tree is a binary search tree that is height balanced: for each

node x

$,$

$$the heights of the left and right subtrees of x differ by at most

$1$

$.$

$$To implement an

AVL tree, maintain an extra attribute h in each node such that x

$.$

h is the height of node x

$.$

As for any other binary search tree T

$,$

$$assume that T

$.$

root points to the root node. Prove that an AVL tree with n nodes has height O$($lg n$).($Hint: Prove that an AVL tree

of height h has at least Fh nodes, where Fh is the h th Fibonacci number.$)$