Implementing a Red-Black Tree Template Class for an Ordered Map in C++

Requirements for Implementing Red-Black Tree Template Class

You are to implement and test a Red-black tree template class to implement an ordered map. Please read the requirements carefully, paying attention to the names and input and output requirements of the class and its methods. We will be testing your class in our test program, so if you do not follow the requirements the test program will not compile, and will not be marked. As usual refer to the General Requirements page - if you have not looked at it recently, look at it again as I may add to it. Maps A map is a container that maps a key to a value, allowing the value to be found efficiently given the key. An ordered map maintains its contents in key order. For this assignment both key and value are to be template variables - and may be of different types; for example, integer keys and string values. Red Black Tree Class Implement a red-black tree template class to store key and value pairs of any type. Your class must be named RedBlackTree. The key should be the first template variable, and the value the second. Public Methods Methods must preserve the red-black and binary search tree properties. default constructor – creates an empty tree whose root is a null pointer copy constructor – a constructor that creates a deep copy of its RedBlackTree reference parameter operator= – overloads the assignment operator for RedBlackTree objects – (deep) copies its RedBlackTree reference parameter into the calling object and returns a reference to the calling object after de-allocating any dynamic memory associated with the original contents of the calling object; if the calling object is the same as the parameter the operator should not copy it destructor – deletes dynamic memory allocated by the tree insert – if the tree does not contain the method's first parameter which represents the key, inserts the key and value (the second parameter) and returns true; otherwise returns false without insertion; i.e. the tree will never contain duplicate keys; note that both key and value are template parameters and may be different types remove – removes the key and associated value from the tree where the key matches the method's single parameter and returns true; if the tree does not contain the a key matching the parameter returns false search – searches the tree for the key that matches the method's single parameter and returns true if it is found and false otherwise search – returns a vector that contains all of the values whose keys are between the method's first and second parameters (including both parameter keys if they are in the tree); the contents of the returned vector are in ascending order of the keys, not the values; if there are no matching keys the returned vector should be empty values – returns a vector that contains all of the values in the tree; the contents of the vector are in ascending key - not value - order; if the tree is empty the returned vector should also be empty keys – returns a vector that contains all of the keys in the tree; the contents of the vector are in ascending order; if the tree is empty the returned vector should also be empty size – returns the number of items stored in the tree getRoot – returns a pointer to the tree's root node – note that this a really bad idea in practice, and in combination with the public NodeT class it allows other programmers access to the internal workings of the tree - again, a really bad thing to do - however it will allow us access to the structure of your tree so that we can make sure that it is correct! File Structure Template classes are often contained in a single .h file as there are compilation issues with breaking them down into separate files, and this is what I want you to do for this assignment. I still want you to keep the implementation separate from the interface as much as possible within this structure, so your method implementations should appear below your RedBlackTree class definition. Your .h file will therefore have this general structure. //include statements // template declaration class NodeT{ //… includes constructor definitions … }; // template declaration class RedBlackTree{ //… }; // RedBlackTree method implementations RedBlackTree::RedBlackTree () { //… } … Additional Notes Your RedBlackTree class should be implemented as discussed in class Calling objects and parameters should be made constant when appropriate Helper methods and attributes of the tree should be made private The RedBlackTree class must have a NodeT pointer attribute for the root of the tree, and an integer attribute that records the size, you may add other attributes as you see fit Method parameters and return values are noted (and highlighted) in the method descriptions – you must not add additional parameters to the methods; if the method description does not mention a parameter it does not have one, similarly if no return value is mentioned the method is void (or a constructor or destructor) Parameter types of some methods, and the type of returned vectors should be your template variables If you are unable to complete a method comment it out and return a default value – i.e. create a stub function Hints As usual write, and test, one (or two) functions at a time For complex methods (such as the insert and remove algorithms) I would suggest writing and testing one or two cases at a time, attempting to write the entire remove method before testing it is likely to result in considerable pain and misery Write your NodeT and RedBlackTree classes as regular (non-template) classes that store base typed keys and values (like integers and characters) first, test them thoroughly and only then convert them into template classes If your insert method does not work we cannot test your class; if you are unable to implement the red-black tree insert algorithm you can still write a bst insert algorithm that will allow us to test your search methods NodeT Class As part of the red black tree implementation you should implement a NodeT class. Your NodeT class must be written in your RedBlackTree.h file, above and outside the RedBlackTree class definition. Your NodeT constructors should be written in the NodeT class definition, and not in a separate NodeT.cpp file. Like your RedBlackTree the NodeT class must also be a template class with two template variables that represent the node's key and value. Nodes should contain the following attributes, which must all be made public, and must be given the names set out below key– a template type parameter value - a template type parameter left – NodeT pointer to the left child right – NodeT pointer to the right child parent – NodeT pointer to the parent isBlack – the colour of the node, either black or red but represented as a bool that is true if the node is black And these methods: Constructor - sets the key and value to its two template type parameters, pointers to null, and isBlack to false You may create other constructors if you wish Simple Test Function Below is a simple test function for your RedBlackTree. If you are unable to compile and run this program it is very likely that we will not be able to compile and run your submission and will therefore not mark your assignment. This test function is not in any way intended to be a comprehensive test of your class so successfully running the program given to you below does not mean that you will get full marks for the assignment. However, it will demonstrate that there is a reasonable probability that we can compile and run your program, allowing us to test each of your methods in detail. void simpleTest() { // Int Tree Tests RedBlackTree<int, char> rb1; if (rb1.insert(6, 'f')) cout << "inserted 42" << endl; rb1.insert(10, 'j'); rb1.insert(2, 'b'); RedBlackTree<int, char> rb2(rb1); if (rb1.remove(2)) cout << "removed 2" << endl; if (rb1.search(6)) cout << "found 6" << endl; vector v1 = rb1.search(8, 21); //should contain j vector v2 = rb1.values(); //should contain {f, j} vector v3 = rb1.keys(); //should contain {6, 10} cout << "size = " << rb1.size() << endl; //should be 2 NodeT<int, char>* pRoot = rb1.getRoot(); //BAD design - for our testing only }