CSSE 230: Session Notes - Day 16
Topics
- Introduction to Red Black
Trees
- Bottom-down insertion into RB tree
- Top-down insertion into RB tree
- Initial analysis of TDRB trees
Outline
- [5 min] Contact before work
- [35 min] Red-black
trees, bottom-up and top-down insertion.
- [15 min] Class exercise: Lopsidedness of RB trees
- [5 min] Break
- [15 min] Class exercise: maximum number of rotations on insertion
into TDRB tree
- [balance of time] Start work on the programming assignment on Top-down Red-Black trees
(Insertion).
Resources