Red Black Tree Source Integration

Spring 2026, UW-Madison

Course Information

• Course Name: Programming III
• Course Number: COMP SCI 400
• Course Instructor: Florian Heimerl

• Session: MWF 3:30 p.m. - 4:20 p.m.
• Course Page

Red Black Tree

Slides

• Red Black Trees
  • Blank slides
  • Filled with instructor's notes
• Red Black Tree Insertion
  • Blank slides
  • Filled with instructor's notes
• Red Black Tree Deletion
  • Blank slides
  • Filled with instructor's notes

Lectures

1. Preview
   • Date: Monday, Jan 26, Week 1
   • Lecture Video - starting Red Black Tree introduction from 41:30
2. Properties, Insertion
   • Date: Wednesday, Jan 28, Week 2
   • Lecture Video
3. Insertion (continued)
   • Date: Friday, Jan 30, Week 2
   • Lecture Video
4. Insertion (continued), Comparison to regular BST
   • Date: Monday, Feb 02, Week 2
   • Lecture Video - ending Red Black Tree topic at 12:30
5. Deletion
   • Date: Wednesday, Feb 04, Week 3
   • Lecture Video - starting Red Black Tree deletion from 25:30
6. Deletion (continued), Complexity analysis for repair operations
   • Date: Friday, Feb 06, Week 3
   • Lecture Video
7. Complexity analysis (continued), RBT operation costs: search, insert, delete
   • Date: Monday, Feb 09, Week 3
   • Lecture Video - ending Red Black Tree topic at 17:30

Supplementary Material

• Red Black Tree insertion algorithm diagram
• Red Black Tree deletion algorithm diagram

Optional Reading

• Red Black Trees
• Wikipedia - Red Black Tree
• Geeks for Geeks - Red Black Tree