CSSE 230: Session Notes - Day 24

Topics

1. AA trees

Outline

1. [5 min] Contact before work
2. [25 min] Introduction to AA-trees, insertion into AA trees
3. [20 min] Removal from AA trees
4. [5 min] Break
5. [5 min] Proof of log height of AA trees.
6. [10 min] Implementing AA trees from the original paper.
7. [balance of time] Work on assignments.

Resources

• Slides
• An applet for AA trees.
• Here is the original paper on AA trees. It is very accessible.
• A video narrating AA trees and insertion into an AA trees
• A video narrating removal from an AA trees
• A video offering hints and tips for implementing AA trees

Homework

1. Day 28, 23:59: AA Trees
   Day 26, BC: Analysis HW