CSSE 230: Session Notes - Day 10
Topics
- AVL Tree removal
- Induction
Outline
- [15 min] Demonstration of removal of elements from
an AVL tree. By hand on the whiteboard and through this applet
- [10 min] Group exercise: Lopsided AVL trees.
- [10 min] Group exercise: Can we have more than one rotation per insert/removal?
- [10 min] Class discussion of number of rotations.
- [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.
- [5 min] Break
- [5 min] Administrative aspects of exam 1
- [30 min] Brief introduction to mathematical induction.
- [25 min] Work on AVL Tree assignment.
Resources
- The two inductive proofs given
in class.
- Slightly more in-depth narrative of
the first proof.
- Video narrating the slides on removing from an AVL tree
- Video explaining the mechanics of removing from an AVL tree
- A video narrating proofs by
induction
Homework
- 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.