CIS-5050 Homework #3: Red-Black Trees

Due: Friday, October 1, 2021

Read Chapter 13 in the text on red-black trees.

  1. Pull an update of the class GitHub repository. You should see a skeleton package for red-black trees and updates to the test program so that the red-black tree tests are executed.

  2. Implement the Check_Sanity procedure to verify the internal structure of the red-black tree it is given. It should verify that the binary search tree property is upheld, that the red-black properties are upheld, and that the handling of Nil is correct.

  3. Implement the two procedures Insert and Delete following the pseudocode in the text. Note that function Search should be complete, but you might want to review it.

Create a zip archive of the files cis5050-redblack_trees.ads and cis5050-redblack_trees.adb. Submit your archive to Canvas.


Last Revised: 2024-11-30
© Copyright 2024 by Peter Chapin <peter.chapin@vermontstate.edu>