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 rb1; if (rb1.insert(6, 'f')) cout << "inserted 42" << endl; rb1.insert(10, 'j'); rb1.insert(2, 'b'); RedBlackTree 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* pRoot = rb1.getRoot(); //BAD design - for our testing only }