CSSE 230: Session Notes - Day 16

Topics

1. Introduction to Red Black Trees
2. Bottom-down insertion into RB tree
3. Top-down insertion into RB tree
4. Initial analysis of TDRB trees

Outline

1. [5 min] Contact before work
2. [35 min] Red-black trees, bottom-up and top-down insertion.
3. [15 min] Class exercise: Lopsidedness of RB trees
4. [5 min] Break
5. [15 min] Class exercise: maximum number of rotations on insertion into TDRB tree
6. [balance of time] Start work on the programming assignment on Top-down Red-Black trees (Insertion).

Resources

• A video introducing Red-Black trees
• A video discussing the implementation of top-down insertion into a red-black tree
• If you want to learn more about RBtrees, here is the paper in which they were proposed.