CSSE 230: Session Notes - Day 11

Topics

• Log height of AVL trees
• Comparison of AVL trees and BST
• Review for exam 1

Outline

• [5 min] Contact before work
• [5 min] Review of BST assignment
• [15 min] Proof of height of AVL Trees.
• [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.
• [5 min] Break
• [20 min] Review for exam 1
• [balance of time] Work on AVL tree assignment.

Resources

• A video narrating the proof of the log height of AVL trees
• Evaluation of BS and AVL trees
• AVL trees a 1 Billion dollar algorithm: Google has 2.5 million servers