AVL Tree Operations

• Label the following BST with AVL balance factors. Is this a properly balanced AVL tree?

  

• Show how the AVL tree below changes when the following operations are applied (in order).

  . insert(B) insert(A) insert(F) insert(E)

  

  
  
  
  
  
  
  

• Imagine that 1,000,000 ($\approx 2^{20}$) keys are added to an initially empty AVL tree. Which of the following could be the height of the resulting tree? (Recall that, for any binary tree, $h(n)\ge \lfloor {\log }_{2}n\rfloor$, and for an AVL tree: $h(n)<1.44{\log }_2(n+2)-.328$)

  • 10, 15, 20, 25, 50, 100, 1000, 1000000

• Consider the following sorting algorithm:

  TreeSort(array)
      -- Insert all items from the provided array into an initially 
         empty AVL tree.
      -- Perform an in-order traversal of the tree, copying all items
         back into the provided array.

  • What is the worst-case big-$\mathrm{\Theta }$ running time of this algorithm?
  • Is it in-place?
  • Is it stable?