CS 3100 Project #4 CS 3100 – Data Structures and Algorithms Project #4 – Indexing with AVL Trees Learning Objectives Demonstrate effective use of memory management techniques in C++ Implement a data...

You have to do it using c++


CS 3100 Project #4 CS 3100 – Data Structures and Algorithms Project #4 – Indexing with AVL Trees Learning Objectives Demonstrate effective use of memory management techniques in C++ Implement a data structure to meet given specifications Design, implement, and use an AVL tree data structure Analyze operations for time complexity Overview Your task for this assignment is to implement an AVL tree that serves as a map data type (sometimes also called a dictionary. A map allows you to store and retrieve key/value pairs. For this project, the key will be an integer and the value will be a string. The AVLTree Class The map will be implemented as an AVL tree. For this project, you must write your own AVL tree - not using code from outside sources. Your AVL tree should remain balanced by implementing single and double rotations when inserting new data. Your tree must support the following operations: bool AVLTree::insert(int key, string value) – Insert a new key/value pair into the tree. For this assignment the duplicate keys are not allowed. This function should return true if the key/value pair is successfully inserted into the map, and false if the pair could not be inserted (for example, due to a duplicate key already found in the map). int AVLTree::getHeight() – return the height of the AVL tree. int AVLTree::getSize() – return the total number of nodes (key/value pairs) in the AVL tree. friend ostream& operator<(ostream& os,="" const="" avltree&="" me)="" -="" print="" the="" tree="" using="" the="">< operator.="" you="" should="" overload="" the="">< operator="" to="" print="" the="" avl="" tree="" “sideways”="" using="" indentation="" to="" show="" the="" structure="" of="" the="" tree.="" for="" example,="" consider="" the="" following="" avl="" tree="" (each="" node="" contains="" a="" key,="" value="" pair):="" 3/9/22,="" 7:05="" pm="" page="" 1="" of="" 3="" this="" tree="" would="" be="" printed="" as="" follows:="" 50,="" fifty="" 45,="" forty-five="" 40,="" forty="" 30,="" thirty="" 20,="" twenty="" 10,="" ten="" (note:="" if="" you="" turn="" your="" head="" sideways,="" you="" can="" see="" how="" this="" represents="" the="" tree.)="" (also="" note:="" this="" style="" of="" printout="" can="" be="" directly="" implemented="" as="" a="" right-child-first="" inorder="" traversal="" of="" the="" tree.)="" bool="" avltree::find(int="" key,="" string&="" value)="" –="" if="" the="" given="" key="" is="" found="" in="" the="" avl="" tree,="" this="" function="" should="" return="" true="" and="" place="" the="" corresponding="" value="" in="" value.="" otherwise="" this="" function="" should="" return="" false="" (and="" the="" value="" in="" value="" can="" be="" anything).=""> AVLTree::findRange(int lowkey, int highkey) – this function should return a C++ vector of strings containing all of the values in the tree with keys ≥ lowkey and ≤ highkey. For each key found in the given range, there will be one value in the vector. If no matching key/value pairs are found, the function should return an empty vector. Example: Suppose the call resultVector = myTree.findRange(30, 47) were called on the tree pictured above. The findRange function would then return a vector containing the strings: {"Thirty", "Fourty", "Forty five"}. Turn in and Grading 3/9/22, 7:05 PM Page 2 of 3 The AVLTree class should use a seperate AVLTree.h and AVLTree.cpp file. Please zip your entire project directory into a single file called project4.zip and upload to the dropbox in Pilot. This project is worth 50 points, distributed as follows: Task Points AVLTree::insert stores key/value pairs in the correct locations in the AVLTree, and correctly rejects duplicate keys 3 AVLTree::getHeight() correctly returns the height of the tree 3 AVLTree::getSize() correctly returns the number of key/value pairs in the tree 3 The tree maintains correct balance, regardless of the order in which keys are inserted 10 operator< prints="" the="" tree="" in="" a="" neat="" and="" readable="" manner,="" using="" indentation="" or="" some="" other="" appropriate="" mechanism="" to="" clearly="" show="" the="" structure="" of="" the="" tree="" 4="" avltree::find="" correctly="" finds="" and="" returns="" key/value="" pairs="" in="" the="" tree="" in="" θ(log="" n)="" time,="" and="" returns="" false="" when="" no="" matching="" key="" is="" found="" 4="" avltree::findrange="" correctly="" returns="" a="" c++="" vector="" of="" strings="" matching="" keys="" in="" the="" specified="" range="" 6="" avltree::operator="correctly" creates="" an="" independent="" copy="" of="" an="" avl="" tree="" 4="" copy="" constructor="" correctly="" creates="" an="" independent="" copy="" of="" an="" avl="" tree="" 4="" code="" has="" no="" memory="" leaks="" 4="" code="" is="" well="" organized,="" well="" documented,="" and="" properly="" formatted.="" variable="" names="" are="" clear,="" and="" readable.="" your="" avltree="" class="" is="" declared="" and="" implemented="" in="" separate="" (.cpp="" and="" .h)="" files.="" 5="" 3/9/22,="" 7:05="" pm="" page="" 3="" of="" 3="" #include="" "avltree.h"="" #include=""> #include using namespace std; int main() { AVLTree tree; cout < tree.insert(50,="" "fifty");="" this="" should="" print="" 0,="" because="" it="" returns="" false="" (no="" duplicates="" allowed):="" cout="">< tree.insert(50,="" "another="" fifty");="" cout="">< tree.insert(100,="" "one="" hundred");="" cout="">< tree.insert(200,="" "two="" hundred");//single="" rotate="" left="" cout="">< "\n\n";="" cout="">< tree="">< endl;="" cout="">< tree.insert(40,="" "fourty");="" cout="">< tree.insert(30,="" "thirty");//single="" rotate="" right="" cout="">< tree.insert(150,="" "one="" hundred="" fifty");="" cout="">< tree.insert(175,="" "one="" hundred="" seventy-five");//double="" rotate="" right="" cout="">< tree.insert(35,="" "thirty-five");="" cout="">< tree.insert(34,"thirty-four");//double="" rotate="" left="" cout="">< tree.insert(50,="" "fifty="" yet="" again");//should="" be="" 0="" cout="">< tree.insert(34,="" "thirty-four="" again");//should="" be="" 0;="" cout="">< tree.insert(200,="" "two="" hundred");//should="" be="" 0;="" expect:="" 1011111111000="" cout="">< "\n\n";="" cout="">< tree="">< endl;="" cout="">< tree.getsize()="">< endl;//9="" cout="">< tree.getheight()="">< endl;//3="" string="" result;="" cout="">< tree.find(50,="" result)="">< endl;//1="" cout="">< result="">< endl;="" fifty="" cout="">< tree.find(40,="" result)="">< endl;//1="" cout="">< result="">< endl;="" fourty="" cout="">< tree.find(175,="" result)="">< endl;//1="" cout="">< result="">< endl;="" one="" hundred="" seventy-five="" cout="">< tree.find(600,="" result)="">< endl;="" 0=""> vec = tree.findRange(30, 200);//all of it for (vector::iterator it = vec.begin(); it != vec.end(); ++it) { cout < *it="">< endl;="" }="" cout="">< "\n\n"="">< endl;="" vec="tree.findRange(100," 200);//right="" subtree="" for="">::iterator it = vec.begin(); it != vec.end(); ++it) { cout < *it="">< endl;="" }="" cout="">< "\n\n"="">< endl;="" vec="tree.findRange(30," 100);//left="" subtree="" for="">::iterator it = vec.begin(); it != vec.end(); ++it) { cout < *it="">< endl;="" 3/9/22,="" 7:05="" pm="" page="" 1="" of="" 2="" }="" cout="">< "\n\n"="">< endl; return 0; } 3/9/22, 7:05 pm page 2 of 2 endl;="" return="" 0;="" }="" 3/9/22,="" 7:05="" pm="" page="" 2="" of="">