In this project you will re-create the Dictionary ADT from pa7, but now based on a Red-Black Tree. Red black trees are covered in Chapter 13 of the text, and will be discussed at length in lecture. All relevant algorithms for RBTs (and BSTs) are posted on the webpage under Examples/Pseudo-code. Aside from having a RBT as its underlying data structure, your Dictionary ADT will have only slight changes to its interface. The recommended approach for this project is to just copy Dictionary.cpp from pa7 and make the necessary changes, but you can start from scratch if you feel it is necessary. The header file Dictionary.his posted in Examples/pa8. It’s most significant difference from the header file for pa7 is a new Node field of type int called color. Other than that, the only difference is a new section for RBT helper functions.
Although these functions are listed as optional, and you may make changes as you like, you should consider them as absolutely necessary for this project.
The top-level client in this assignment is again called Order.c, and is identical to that of pa7. No changes should be necessary. Again, five pairs of input-output files are given in Example/pa8, along with a random input file generator. Note that the input files are identical to those of pa7, but the paired outputs are different.
In particular, the output file sections giving all keys in a pre-order traversal are different, since the trees are now balanced by the RBT algorithms.
Also, as before, a test client called DictionaryClient.cpp is posted in Examples/pa8. This program is more extensive than the pa7 version, testing the remove() operation much more thoroughly. You should still consider it a weak test of the Dictionary ADT however, and as always, design your own tests. There is one very small change from pa7 that should be mentioned. The pre-condition error messages for operations next() and prev() are worded slightly differently (so as to be consistent with those of currentKey()and currentVal().) These changes will be apparent from the output file DictionaryClient-out, which is also included in Examples/pa8.
Altogether this should be a straightforward assignment, especially if pa7 went well for you. Submit the following 6 files in the usual manner before the end of the grace period.
- README Written by you, a catalog of submitted files and any notes to the grader
- Makefile Provided, alter as you see fit
- Dictionary.h Provided, you may alter the “helper functions” sections, but nothing else
- Dictionary.cpp Written by you, the majority of work for this project
- DictionaryTest.cpp Written by you, your test client of the Dictionary ADT
- Order.cpp Written by you, the client for this project
As usual, do not turn in any executable files, binaries, or anything not listed above. Good luck.