CSSE 230: Session Notes - Day 10

Topics

  1. AVL Tree removal
  2. Induction

Outline

  1. [15 min] Demonstration of removal of elements from an AVL tree. By hand on the whiteboard and through this applet
  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. [5 min] Administrative aspects of exam 1
  8. [30 min] Brief introduction to mathematical induction.
  9. [25 min] Work on AVL Tree assignment.

Resources

  1. The two inductive proofs given in class.
  2. Slightly more in-depth narrative of the first proof.
  3. Video narrating the slides on removing from an AVL tree
  4. Video explaining the mechanics of removing from an AVL tree
  5. A video narrating proofs by induction

Homework

  1. Day 11, BC: Complete the proofs for items 3-6 of: Induction HW. Please submit a pdf copy of your work and please place your name near the top of your document. Submissions that do not satisfy these two constraints will not be graded. Thank you.