CSSE 230: Session Notes - Day 17

Topics

1. AA trees

Outline

1. [5 min] Contact before work
2. [25 min] Removal from AA trees
3. [10 min] Maximum number of rotations on removal
4. [15 min] Deep analysis of AA Trees
5. [15 min] Implementing AA Trees
6. [5 min] Break
7. [balance of time] Work on assignments.

Resources

• Slides
• Deep Analysis of AA trees
• An animation for AA trees.
• Here is the original paper on AA trees. It is very accessible.
• A video narrating removal from an AA trees
• A video offering hints and tips for implementing AA trees