Project 4
Fall 2020
Due: F 11/13 @ 5 PM
10 points
Building on your implementation for p2, implement Goodrich et al.'s algorithms for red-black trees as the class RBTree<T>.
I put some starter code on cs-class, which you can retrieve using the command:
cs-class% cp ~maloofm/cosc160/p4.zip ./
I strongly recommend that you use sentinel nodes to represent external nodes for this project. To use sentinel nodes, you will need to make minor modifications to the TreeNode, Position, and Iterator classes from p2 to encapsulate and use the pointer to the RBTree<T>::sentinel.
You also need to add a color attribute to TreeNode. I used an enumeration (enum) in my implementation of RBNode. Feel free to do something else, as long as you do not use strings.
If you need additional examples of insertions and removals, I posted two videos on YouTube: Red-black Trees.
Instructions for Electronic Submission: In a file named HONOR, please include the statement:
In accordance with the class policies and Georgetown's Honor Code, I certify that, with the exceptions of the class resources and those items noted below, I have neither given nor received any assistance on this project.Include this file in your zip file submit.zip.
Submit p4 exactly like you submitted p3. Make sure you remove all debugging output before submitting.
If something goes wrong with Autolab, upload your zip file to Canvas.
Copyright © 2020 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.