CIS-5050 Homework #3: Red Black Trees

Due: Friday, March 6, 2020

Read Chapter 13 in the text on red black trees.

  1. Unzip the following three archives, in order, in your sample workspace:

    1. binary search trees.
    2. The skeletal red black trees package.
    3. The KV_Stores testing infrastructure also comes with test programs for skip lists, binary search trees, redblack trees, and splay trees. This archive does not come with a skip list implementation (to avoid overwriting your work from Homework #2)

    Let the later archives overwrite any files created by the earlier archives (they are newer versions of those files).

  2. In the package body for RedBlack_Trees implement the two procedures Insert and Delete following the pseudo-code in the text.

  3. Optional. 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.

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


Last Revised: 2020-02-11
© Copyright 2020 by Peter C. Chapin <pchapin@vtc.edu>