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-\(\Theta\) running time of this algorithm?
  • Is it in-place?
  • Is it stable?