n class, we discuss the main ideas that are needed to prove that an AVL tree with n nodes

has height O$($log n$).$ Give the best upper bound you can find on the height of an AVL tree

with n nodes. The upper bound that you give should be of the form c $$ log$2($n $+$ k$)+$ b$,$ where

c$,$ k$,$ b are constants. Provide a careful and very thorough justification of every step.

Note: Recall that for AVL trees we use the following definition: The height of a tree is the

number of nodes in the longest path from the root to a leaf.

$3$