CSSE 230: Session Notes - Day 13

Topics

• Log height of AVL trees
• Comparison of AVL trees and BST

Outline

• [5 min] Contact before work
• [5 min] Review of BST assignment
• [30 min] Brief introduction to mathematical induction.
• [15 min] Proof of height of AVL Trees.
• [5 min] Break
• [15 min] Best, worst, avg case analysis of AVL tree operations.
• [20 min] Comparison of BST and AVLTrees: Inserting, finding and removing 1 Mio elements.
• [balance of time] Work on AVL tree assignment.

Resources

• The two inductive proofs given in class.
• Slightly more in-depth narrative of the first proof.
• A video narrating proofs by induction
• A video narrating the proof of the log height of AVL trees
• Evaluation of BS and AVL trees.

Homework

1. Day 15, 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.