September 4, 2024
Wednesday of Week 2
Topic of the day
- Red-black tree implementation cases
Online references
- Slides on 234/RB insertion cases (www.cs.purdue.edu)
- RB insertion and deletion with 234 correspondences (English is imperfect but examples are very good) (yuyuan.org)
- RB insertion (with examples) (cs.valdosta.edu)
Questions and exercises
- What does "rotation" mean in the context of binary search tree manipulation? Draw an example to illustrate your answer.
- What are the two ways that a 3-node can be represented in a red-black tree? Why is this a source of complication when implementing red-black trees?
Assignments
Upcoming
- Project 1: Balanced binary due (11 Sep)
- Project 2: Markov babbler out (11 Sep)
