CMPT 225 Assignment 5 Red Black Trees
assignment | 代做c++ | 数据结构代写 – 这个题目属于一个红黑树的代写任务, 是比较有代表性的红黑树等代写方向, 这是值得参考的assignment代写的题目
You are to implement and test a red-black tree template class. This assignment is worth 7 % of your grade.
Please read the requirements carefully, as usual pay 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, and if you do not follow the requirements this test program may not compile, and your class may therefore not be marked.
Red Black Tree Class
Implement a red-black tree template class to store data of any (comparable) type. Your class must be named RedBlackTree.
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 single parameter , inserts the parameter and returns true ; otherwise does not insert the parameter and returns false ; i.e. the tree will never contain duplicate values remove removes the method’s parameter from the tree and returns true ; if the tree does not contain the parameter returns false search searches the tree for 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 between the method’s first and second parameters (including both parameter values if they are in the tree); the contents of the returned vector are in ascending order; if there are no such values the returned vector should be empty dump returns a vector that contains all of the values 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 Node class it allows other programmers access
to the internal workings of the tree (again, a really bad thing to do ), however it does 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 variable 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 a base type (like an int ) first, test them thoroughly and only then convert them into template classes The dump method entails an in-order traversal of the tree
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. Since your RedBlackTree data type is given by a template parameter the Node class must also be a template class.
Nodes should contain the following attributes, which must all be made public, and must be given the names set out below data a template type parameter left Node pointer to the left child right Node pointer to the right child parent Node 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 data to its template type parameter , references to null pointers, and isBlack to false You may create other constructors if you wish
Simple Test Function
Below is a simple test function for your RB tree. 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. Read the paragraph below.
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(42)) cout << “inserted 42” << endl; rb1.insert(71);
rb1.insert(13); RedBlackTree rb2(rb1);
if (rb1.remove(13)) cout << “removed 13” << endl; if (rb1.search(42)) cout << “found 42” << endl;
vector v1 = rb1.search(50, 100); //should contain 71 vector v2 = rb1.dump(); //should contain {42,71}
cout << “size = ” << rb1.size() << endl; //should be 2 NodeT* pRoot = rb1.getRoot(); //BAD design – for our testing only }
Assessment
The assignment is out of 6 2.
Structure 5 marks Copy constructor and overloaded assignment operator 5 marks Mutators insert (5), remove (5) 10 Accessors search (4 each), dump (4), size (2) – 14 Template 5 marks Memory management 5 Code style 18 marks (comments, naming, indentation and class design) see the code quality page for more detail.
Compilation We will test your projects in Linux and use the g++ compiler with the – std=C++11 flag to compile them. While you are welcome to develop your solution in whatever environment you prefer you should make sure it can be compiled and run as described above. Solutions that cannot be compiled will not be marked. If you are unable to write a method, write a stub function for it. If you are unable to complete a method, comment out the non-functional sections of the method so that you receive marks for any test cases the method is able to pass.
Memory Management We will run your program using valgrind. If your program shows memory errors, you will lose the five marks allocated to memory management.
Submission
You should submit your assignment online to the CoursSys submission server. You must submit your RedBlackTree.h file, please read the documentation on site for further information. The assignment is due by Wednesday April 8th at 11:59pm.
If you are unable to complete one of the methods, make sure that any calls to that method will still compile and run by writing a stub function for that method.
CMPT 225 Home
John Edgar ([email protected])