AVL Trees Exercises

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, 11, 2, 10, 3, 9, 4, 8, 5, 7, 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: