CIS-5050 Homework #3: Red Black Trees

Due: Monday, October 15, 2018

Read Chapter 13 in the text on red black trees.

  1. I provide a package specification and a skeletal package body for RedBlack_Trees in this zip archive. Unpack the archive in the src folder of the sample project. Implement the three procedures Search, Insert, and Delete following the pseudo-code in the text.

  2. Implement a RedBlack_Trees.Check package following the example provided for skip lists. You can probably start by copying the skip lists Check package and modifying it. You will need to overhaul the Is_Sane function. Also add some test cases to the Check program (don't remove the skip list tests). Ideally your test should be designed so that they exercise all the cases in the code.

  3. We should evaluate the performance of your implementation. We will defer that evaluation until the next assignment.

Create a zip archive of the files, redblack_trees.adb,, redblack_trees-check.adb, and check.adb. Submit your achive to Moodle.

Last Revised: 2018-09-26
© Copyright 2018 by Peter C. Chapin <>