CSSE 230: Session Notes - Day 11

Topics

  1. AVL Tree removal
  2. Initial analysis of AVL Trees

Outline

  1. [15 min] Demonstration of removal of elements from an AVL tree. By hand on the whiteboard and through this annimation
  2. [10 min] Group exercise: Lopsided AVL trees.
  3. [10 min] Group exercise: Can we have more than one rotation per insert/removal?
  4. [10 min] Class discussion of number of rotations.
  5. [5 min] When the height difference of the grandchildren is equal, you must choose a single rotation. This case can only happen on removal. See also Wikipedia entry on AVL trees.
  6. [5 min] Break
  7. [25 min] Work on AVL Tree assignment.

Resources

  1. Video narrating the slides on removing from an AVL tree
  2. Video explaining the mechanics of removing from an AVL tree