CSSE 230: Session Notes - Day 16

Topics

1. AA trees

Outline

1. [5 min] Contact before work
2. [25 min] Introduction to AA-trees, insertion into AA trees
3. [10 min] Lopsidedness of AA trees
4. [10 min] Maximum number of rotations on insert
5. [5 min] Break
6. [5 min] Proof of log height of AA trees.
7. [balance of time] Work on assignments.

Resources

• Slides
• An animation 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