Module 5: Red-Black Trees

Welcome to Module 5

In Data Structures & Algorithms, we learned how to create a binary search tree, which support efficient adding, searching, and traversing in sorted order. Although a binary search tree can exhibit O(lg n) behavior (performance on the order of the height of the tree) for adding and searching, that may degrade to O(n) if the tree is not balanced. Red-black trees represent a way to mark tree nodes with a binary value and use that value as part of modified insertion (and removal) procedures to keep the tree approximately balanced.

Module Learning Outcomes

Upon successful completion of this module, you will be able to:

  1. Maintain a pointer to a nodes parent in a tree data structure (CLO 2).
  2. Trace subtree rotations in a diagram in a red-black tree (CLO 2)
  3. Insert/delete nodes in a binary search tree while maintaining a balanced tree (CLO 2).

(CLO = Course Learning Outcome)

To Do

Please read/watch all of the module learning materials (readings, presentations, videos, etc.) and complete all assignments/assessments listed below. If you have questions, please contact the course instructor or ask in the Questions About This Course forum.

Readings and Presentations:

  • Read Chapter 13 (Review Chapter 12 concerning binary search trees as needed)
  • Topic 5: Red-Black Trees Online Lecture

Assignments/Assessments:

  • Exercise 4: Binary Search Trees
  • Questions 1: Sorting

Click the Next ▶ button to continue.