In C++ a4main.cpp
Posted: Sun Jul 10, 2022 11:26 am
In C++
a4main.cpp
You are to implement and test an AVL 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. This assignment is likely to take longer than the previous assignments so I'd recommend starting early. Also, read the hints at the end of the document (and the rest of the document of course). Files You are provided with two files, AVLTree.h and a4main.cpp. The .cpp file contains a simple - but woefully inadequate - test of your AVL tree methods. The major use of this test is so that you can confirm that you have followed the basic requirements of the class. You are to complete the AVLTree.h. It contains empty class definitions for your AVLTree and AVLTreeNode classes. You should add to these, but not change them - do not delete or comment out the getRoot method. • AVLTree.h a4main.cpp 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. AVL Tree Class Implement an AVL tree template class to store key and value pairs of any type. Your class must be named AVLTree. The key type should be the first template variable, and the value type the second. Your AVLTree must have a private AVLTreeNode pointer named root. It may have other attributes Public Methods Methods must preserve the AVL balance 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 AVLTree reference parameter. operator= - overloads the assignment operator for AVLTree objects to make a deep copy of its AVLTree reference parameter and return a reference to the calling object. The operator should behave correctly under self assignment. 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 does not contain duplicate keys; both both key and value should be template parameters and may be different types • remove - removes the key and associated value from the tree where the key matches the method's 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 equals the method's single parameter, returning the corresponding value if it is found and throwing a runtime_error exception if it is not • 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 an unsigned int equal to the number of items stored in the tree
• getRoot - this method is provided to you in the .h file and you should not change it in any way. It returns a pointer to the tree's root node. Note that this violates class design principles, and in combination with the public AVLTreeNode class it allows other programmers access to the internal workings of the tree - again, not something to do in practice. Its purpose is to allow us access to the structure of your tree so that we can make sure that it is a valid AVL tree. 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 AVLTree class definition as indicated in the provided file. Additional Notes • Method parameters and return values are noted in the method descriptions - you must not add additional parameters to the methods (or change the return values). 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). Note that some of the parameter and return types should be template variables. • Your AVLTree class should be implemented as described in class. • The AVLTree class must have an AVLNode pointer attribute for the root of the tree, and an unsigned integer attribute that records its size, you may add other attributes as you see fit. • Calling objects and parameters should be made constant when appropriate. • Helper methods and attributes of the tree should be made private. • Marks will be deducted if your implementation fails to deallocate dynamic memory when appropriate. • If you are unable to complete a method return a default value - i.e. create a stub function. AVLTreeNode Class As part of the AVL tree implementation you should implement an AVLTreeNode class. The declaration of the AVLTreeNode class should be included in the AVLTree.h file, as indicated in the provided.h file. Like your AVLTree, the AVLTreeNode class must also be a template class with two template variables that represent a 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 - AVLTreeNode pointer to the left child right-AVLTreeNode pointer to the right child • parent - AVLTreeNode pointer to the parent • height - an unsigned int that represents the height of the node And these methods: • Constructor - sets the key and value to its two template type parameters, pointers to nullptr, and height to zero • You may create other constructors if you wish Submission You should submit your assignment online as a (single) AVLTree.h. 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.
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 method before testing it is likely to result in considerable pain and misery. • Write helper methods for left and right rotations of nodes. • Implement BST insert and remove first (i.e. without rotations). Even if you only manage to implement a BST (rather than an AVL tree) you should receive a substantial number of the marks. This is particularly important for insert as if your insert method does not work we cannot test your class. • Write your AVLTreeNode and AVLTree 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 - this is the method recommended by Bjarne Stroustrup. • When you test your template class make sure you test it with non-numeric types for both keys and values.
- In C A4main Cpp 1 (418.93 KiB) Viewed 45 times
- In C A4main Cpp 2 (400.89 KiB) Viewed 45 times
- In C A4main Cpp 3 (68.34 KiB) Viewed 45 times
You are to implement and test an AVL 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. This assignment is likely to take longer than the previous assignments so I'd recommend starting early. Also, read the hints at the end of the document (and the rest of the document of course). Files You are provided with two files, AVLTree.h and a4main.cpp. The .cpp file contains a simple - but woefully inadequate - test of your AVL tree methods. The major use of this test is so that you can confirm that you have followed the basic requirements of the class. You are to complete the AVLTree.h. It contains empty class definitions for your AVLTree and AVLTreeNode classes. You should add to these, but not change them - do not delete or comment out the getRoot method. • AVLTree.h a4main.cpp 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. AVL Tree Class Implement an AVL tree template class to store key and value pairs of any type. Your class must be named AVLTree. The key type should be the first template variable, and the value type the second. Your AVLTree must have a private AVLTreeNode pointer named root. It may have other attributes Public Methods Methods must preserve the AVL balance 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 AVLTree reference parameter. operator= - overloads the assignment operator for AVLTree objects to make a deep copy of its AVLTree reference parameter and return a reference to the calling object. The operator should behave correctly under self assignment. 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 does not contain duplicate keys; both both key and value should be template parameters and may be different types • remove - removes the key and associated value from the tree where the key matches the method's 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 equals the method's single parameter, returning the corresponding value if it is found and throwing a runtime_error exception if it is not • 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 an unsigned int equal to the number of items stored in the tree
• getRoot - this method is provided to you in the .h file and you should not change it in any way. It returns a pointer to the tree's root node. Note that this violates class design principles, and in combination with the public AVLTreeNode class it allows other programmers access to the internal workings of the tree - again, not something to do in practice. Its purpose is to allow us access to the structure of your tree so that we can make sure that it is a valid AVL tree. 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 AVLTree class definition as indicated in the provided file. Additional Notes • Method parameters and return values are noted in the method descriptions - you must not add additional parameters to the methods (or change the return values). 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). Note that some of the parameter and return types should be template variables. • Your AVLTree class should be implemented as described in class. • The AVLTree class must have an AVLNode pointer attribute for the root of the tree, and an unsigned integer attribute that records its size, you may add other attributes as you see fit. • Calling objects and parameters should be made constant when appropriate. • Helper methods and attributes of the tree should be made private. • Marks will be deducted if your implementation fails to deallocate dynamic memory when appropriate. • If you are unable to complete a method return a default value - i.e. create a stub function. AVLTreeNode Class As part of the AVL tree implementation you should implement an AVLTreeNode class. The declaration of the AVLTreeNode class should be included in the AVLTree.h file, as indicated in the provided.h file. Like your AVLTree, the AVLTreeNode class must also be a template class with two template variables that represent a 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 - AVLTreeNode pointer to the left child right-AVLTreeNode pointer to the right child • parent - AVLTreeNode pointer to the parent • height - an unsigned int that represents the height of the node And these methods: • Constructor - sets the key and value to its two template type parameters, pointers to nullptr, and height to zero • You may create other constructors if you wish Submission You should submit your assignment online as a (single) AVLTree.h. 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.
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 method before testing it is likely to result in considerable pain and misery. • Write helper methods for left and right rotations of nodes. • Implement BST insert and remove first (i.e. without rotations). Even if you only manage to implement a BST (rather than an AVL tree) you should receive a substantial number of the marks. This is particularly important for insert as if your insert method does not work we cannot test your class. • Write your AVLTreeNode and AVLTree 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 - this is the method recommended by Bjarne Stroustrup. • When you test your template class make sure you test it with non-numeric types for both keys and values.