In this assignment you will implement AVL trees. You are responsible for implementing insertion and deletion, so you are also responsible for rotating subtrees to maintain the balance property, find the minimum, and a few additional auxiliary methods. In assignment3.zip, we are providing you with the following code: avl. cpp -> your AVL implementation, mostly dummy text avl. hpp -> header file, you do not have to change it avl. cpp already has a couple methods implemented that you should not change: • a method to print trees, and . a main method that reads test cases (sequences of operations) and executes them A sample README file is also provided. You may find how to compile and test the code. We will test your implementation with test cases that spell out operations (insert a number, delete a number, and print) to be executed on an (initially) empty AVL tree. For example, insert 100 insert 30 insert 20 insert 50 print delete 30 print insert 990 insert 900 print means that you should insert 100, 30, 20, 50 and print the resulting AVL tree. Then you should delete 30 and print the resulting AVL tree. Finally, you need to insert 990 and 900 and print the resulting AVL tree. The expected outcome is the following: 30 11 20 Ir 100 | |1 50 50 11 20 Ir 100 50 11 20 Ir 900 1 100 | Ir 990 where the last tree has root 50 and two children: 20 and 900, and node 900 has two children: 100 and 990. Also, 50 is the left child of 100 in the first tree. A few more notes: • We will publish more complex test cases three days prior to the submission deadline. I recommend you run the examples we saw in class by yourself. • Your insertion and deletion must run in O(log(n)), and you must update the height of nodes after each operation. Opportunity for extra credits (up to 25 points): Write a program that checks whether a binary search tree is an AVL. The input is an arbitrary binary search tree, and the output is binary, so, either true of false. #include #include #include "avl. hpp" using namespace std; #define IS_ROOT O #define IS_LEFT 1 #define IS_RIGHT 2 O ** * * Internal method to insert into a subtree. x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ void insert( const int & info, AvlNode * & root ) { std::cout << "As of now, I am implementing a dummy insert" «< endl; std::cout << "Code for inserting " « info «< goes here" << endl; 11 == if (root NULL) root = new AvlNode (info, NULL, NULL); else if (info % 2 == 0){ // for now, even numbers to the left ... [CHANGE THIS] insert( info, root->left ); • } else { // and off numbers to the right [CHANGE THIS] insert( info, root->right ); } Internal method to remove from a subtree. * info is the item to remove. * root is the node that roots the subtree. Set the new root of the subtree. */ Ovoid remove( const int & info, AvlNode * & root ) { std::cout << "Code for deleting " «< info << " goes here" << endl; 1/* * You will probably neesd auxiliary mathods to find the minimum of tree rotate (single and double, in both directions balance am AVL tree * == == /* * Print methods, do not change */ void print (AvlNode *root, int level, int type) { if (root NULL) { return; } if (type IS_ROOT) { std::cout << root -> element << "\n"; } else { for (int i 1; i < level; i++) { std::cout << "|"; } if (type IS_LEFT) { std::cout << "|1_" «< root -> element << "\n"; } else { std::cout << "Ir_" «< root -> element << "\n"; } 40- == if (root -> left != NULL) { print(root -> left, level + 1, IS_LEFT); } if (root -> right != NULL) { print(root -> right, level + 1, IS_RIGHT); } } void print (AvlNode *root) { print(root, 0, IS_ROOT); } * END Print methods, do not change * Main method, do not change == int main(int argc, const char * argv[]) { AvlNode *root = NULL; std::string filename argv[1]; freopen(filename. c_str(), ",", stdin); std::string input; int data; while(std::cin >> input){ if (input "insert"){ std::cin>>data; insert(data, root); } else if(input == "delete"){ std::cin>>data; remove(data, root); } else if(input "print"){ print (root); std::cout << "\n"; } else{ std::cout<<"Data not consistent in file"; break; == Estruct AvlNode { int element; AvINode *left; AvlNode *right; int height; AvlNode (const int & ele, AvlNode *lt, Av Node *rt, int h = 0) { element ele; left lt; right = rt;