AVL Trees Exercises

   < Previous  Next >
  1. Discuss with your neighbor:
    1. What an AVL tree is (and is not)
    2. The main advantage(s) of using an AVL tree
    3. The Big-Ohs for AVL tree operations:
      Average-case Worst-case
      Retrieval    
      Insertion    
      Deletion    
      Traversal    
  2. Review the AVL rotations handout
  3. Insert the numbers 1, 2, ... 10 into an AVL tree.
    Draw the tree after each insertion.
    If appropriate, identify
    1. the imbalanced node
    2. what type of rotation is needed
    Double check that
    1. after each rotation that it's a BST
    2. after each insertion that it's an AVL tree
  4. Insert the numbers 10, 9, ... 5 into an AVL tree.
    Draw the tree after each insertion.
    If appropriate, identify
    1. the imbalanced node
    2. what type of rotation is needed
  5. Insert the numbers 1, 10, 2, 9, 3, 8, 4, 7, 5, 6 into an AVL tree.
    Draw the tree after each insertion.
    If appropriate, identify
    1. the imbalanced node
    2. what type of rotation is needed

Last Modified: