how to do this in c++ programming? HELP with explanation of the code!! 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 of methods implemented that you **should not change**:- A method to print trees- A main method that reads test cases (sequences of operations) and executes themA 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 100insert 30insert 20insert 50printdelete 30printinsert 990insert 900print```This 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| l 20| r 100| | l 50```**Explanation of the AVL Tree Diagram:**- The root node is **30**.- Node **20** is the left child of 30.- Node **100** is the right child of 30.- Node **50** is the left child of 100. This visual structure represents the balanced nature of AVL trees, where each node maintains the AVL property of balanced subtrees. ### Binary Tree Structures#### Tree 1:- **Root Node**: 50 - **Left Child**: 20 - **Right Child**: 100 #### Tree 2:- **Root Node**: 50 - **Left Child**: 20 - **Right Child**: 900 - **Left Child of 900**: 100 - **Right Child of 900**: 990The second tree's structure is such that the root node is 50. It has two children: 20 and 900. The node 900 further has two children: 100 and 990. Additionally, in Tree 1, node 50 is the left child of node 100.

C++ code of AVL Treeavl.cpp: #include <stdio.h>#include <iostream>#include "avl.hpp"using namespace std; #define IS_ROOT 0#define IS_LEFT 1#define IS_RIGHT 2 void balance(AvlNode *& node);int max(int a, int b);int height(AvlNode* node);/*** 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.*/// change this to a node function to allow assignment from the result to a node variableAvlNode* 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;if (root == NULL)root = new AvlNode (info, NULL, NULL);else if (info < root->element){root->left = insert( info, root->left );} else {root->right = insert( info, root->right );} root->height = max(height(root->left), height(root->right)) + 1; //get the height of the treebalance(root); // balance tree after iinsertionreturn root;} /*** 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.*/void remove( const int & info, AvlNode * & root ) {std::cout << "Code for deleting " << info << " goes here" << endl; AvlNode *removal = root; // initialize removal nodeAvlNode *parent = new AvlNode (0, NULL, NULL); //initialize tracks parent of removalint type; //relationship between parent and removal if(root == NULL)return; while(removal->element != info){ //find the removal node with the right keyif(removal == NULL)return; /*never found*/ parent = removal; // set parent to the previous removal nodeif(info < removal->element){ // go left if node is biggerremoval = removal->left;type = IS_LEFT;} else { // go rightremoval = removal->right;type = IS_RIGHT;}} if(info == removal->element){ while (removal->right != NULL && removal->left != NULL){ // node has both left and right child parent = removal; //go to the removal child of parentremoval = removal->left; //go to left of the romoval nodeparent->element = removal->element; // update the removal elementtype = IS_LEFT; } if(removal->right == NULL && removal->left != NULL){ // if node has a left child if(type == IS_LEFT){parent->left = removal->left;} else{parent->right = removal->left;} } else if(removal->left == NULL && removal->right != NULL){ // if node has a right childcout << "test" << endl;if (type == IS_LEFT){parent->left = removal->right;} else{parent->right = removal->right;} } else if(removal->left == NULL && removal->right == NULL){ //if node has no childif (type == IS_LEFT){parent->left = NULL;} else{parent->right = NULL;} } elsestd::cout << "error" << endl; }balance(root); // balance tree after deletion} /** You will probably neesd auxiliary mathods to* - find the minimum of tree* - rotate (single and double, in both directions* - balance am AVL tree*/// find heightint height(AvlNode* node){ // needed because the you can acces the height of a null node(doesn't exist)if(node == NULL) // if the node is null exitreturn 0; // return 0else // otherwisereturn node->height; // return height}// find the maximum of the two integersint max(int a, int b){return (a > b) ? a : b;}// find the minimumint minimum(AvlNode *& root){while(root->left != NULL){root = root->left;}return root->element;} // right rotate singleAvlNode* rotateRight(AvlNode *& node){AvlNode *leftchild = node->left;// rotate with the left childnode->left = leftchild->right;leftchild->right = node;//update heightnode->height = max(height(node->left), height(node->right)) + 1;leftchild->height = max(height(leftchild->left), height(leftchild->right)) + 1;// update nodenode = leftchild;return node;} // left rotate singleAvlNode* rotateLeft(AvlNode *& node){AvlNode *rightchild = node->right;// rotate with the right childnode->right = rightchild->left;rightchild->left = node;// update heightnode->height = max(height(node->left), height(node->right)) + 1;rightchild->height = max(height(rightchild->left), height(rightchild->right)) + 1;//update nodenode = rightchild;return node;} // double right rotatevoid doubleRight(AvlNode *& node){node->left = rotateLeft(node->left);node = rotateRight(node);} // double left rotate nodevoid doubleLeft(AvlNode *& node){node->right = rotateRight(node->right);node = rotateLeft(node);} // balnce the avl treevoid balance(AvlNode *& node){if (node == NULL)return;/*NULL root*/ if(height(node->left) - height(node->right) > 1){ // if height of the left is larger with a diference greater than 1if(height(node->left->left) >= height(node->left->right))/*balance left*/ // left child of the left node is greaterrotateRight(node); // single right rotateelse // otherwisedoubleRight(node); // double right rotate } else if(height(node->right) - height(node->left) > 1){ // if the height of the right is larger with a difference greater than 1if(height(node->right->right) >= height(node->right->left))/*balance right*/ // right child of the right node is greaterrotateLeft(node); // single left rotateelse // otherwisedoubleLeft(node); // double left rotate}} /** 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 << "|l_" << root -> element << "\n";} else {std::cout << "|r_" << root -> element << "\n";}}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(), "r", 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;}}return 0;}/** END main method*/ avl.hpp: struct AvlNode {int element;AvlNode *left;AvlNode *right;int height; AvlNode (const int & ele, AvlNode *lt, AvlNode *rt, int h = 0) {element = ele;left = lt;right = rt;}}; isAvl.cpp: #include <stdio.h>#include <iostream>#include "avl.hpp"using namespace std; #define IS_ROOT 0#define IS_LEFT 1#define IS_RIGHT 2 bool balance(AvlNode *& node);int max(int a, int b);int height(AvlNode* node);/*** 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.*/// change this to a node function to allow assignment from the result to a node variableAvlNode* 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;if (root == NULL)root = new AvlNode (info, NULL, NULL);else if (info < root->element){root->left = insert( info, root->left );} else {root->right = insert( info, root->right );} root->height = max(height(root->left), height(root->right)) + 1; //get the height of the tree// if( balance(root) )// std::cout << "true" << endl;// else// std::cout << "false" << endl;return root;}/*** 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.*/void remove( const int & info, AvlNode * & root ) {std::cout << "Code for deleting " << info << " goes here" << endl; AvlNode *removal = root; // initialize removal nodeAvlNode *parent = new AvlNode (0, NULL, NULL); //initialize tracks parent of removalint type; //relationship between parent and removal if(root == NULL)return; while(removal->element != info){ //find the removal node with the right keyif(removal == NULL)return; /*never found*/ parent = removal; // set parent to the previous removal nodeif(info < removal->element){ // go left if node is biggerremoval = removal->left;type = IS_LEFT;} else { // go rightremoval = removal->right;type = IS_RIGHT;}} if(info == removal->element){ while (removal->right != NULL && removal->left != NULL){ // node has both left and right child parent = removal; //go to the removal child of parentremoval = removal->left; //go to left of the romoval nodeparent->element = removal->element; // update the removal elementtype = IS_LEFT; } if(removal->right == NULL && removal->left != NULL){ // if node has a left child if(type == IS_LEFT){parent->left = removal->left;} else{parent->right = removal->left;} } else if(removal->left == NULL && removal->right != NULL){ // if node has a right childcout << "test" << endl;if (type == IS_LEFT){parent->left = removal->right;} else{parent->right = removal->right;} } else if(removal->left == NULL && removal->right == NULL){ //if node has no childif (type == IS_LEFT){parent->left = NULL;} else{parent->right = NULL;} } elsestd::cout << "error" << endl; }}// find heightint height(AvlNode* node){ // needed because the you can acces the height of a null node(doesn't exist)if(node == NULL) // if the node is null exitreturn 0; // return 0else // otherwisereturn node->height; // return height}// find the maximum of the two integersint max(int a, int b){return (a > b) ? a : b;} // balnce the avl treebool balance(AvlNode *& node){if (node == NULL)return true;/*NULL root*/ if(height(node->left) - height(node->right) > 1){ // if height of the left is larger with a diference greater than 1return false;} else if(height(node->right) - height(node->left) > 1){ // if the height of the right is larger with a difference greater than 1return false;} elsereturn true;} /** 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 << "|l_" << root -> element << "\n";} else {std::cout << "|r_" << root -> element << "\n";}}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(), "r", 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;}}if( balance(root) )std::cout << "It is an Avl" << endl;elsestd::cout << "Not an Avl" << endl;return 0;}/** END main method*/ treeAvl.cpp: #include <stdio.h>#include <iostream>#include <regex>#include <vector>#include "avl.hpp"using namespace std; #define IS_ROOT 0#define IS_LEFT 1#define IS_RIGHT 2 // globalvector<string> inputs;vector<int> values; bool balance(AvlNode *& node);int max(int a, int b);int height(AvlNode* node);/*** 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.*/// change this to a node function to allow assignment from the result to a node variableAvlNode* insert(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;AvlNode* node = root;string input = inputs.back();inputs.pop_back();info = values.back();values.pop_back();if (input == "|l_"){values.push_back(info);inputs.push_back("root");root->left = insert( info, root->left ); } else if(input == "|r_"){values.push_back(info);inputs.push_back("root");root->right = insert( info, root->right ); } else if(input == "root"){info = stoi(input, nullptr, 10);root = new AvlNode (info, NULL, NULL);node = root;} // if (root == NULL)// root = new AvlNode (info, NULL, NULL);// else if (info < root->element){// root->left = insert( info, root->left );// } else {// root->right = insert( info, root->right );// } root->height = max(height(root->left), height(root->right)) + 1; //get the height of the tree// if( balance(root) )// std::cout << "true" << endl;// else// std::cout << "false" << endl;return root;}// find heightint height(AvlNode* node){ // needed because the you can acces the height of a null node(doesn't exist)if(node == NULL) // if the node is null exitreturn 0; // return 0else // otherwisereturn node->height; // return height}// find the maximum of the two integersint max(int a, int b){return (a > b) ? a : b;} // balnce the avl treebool balance(AvlNode *& node){if (node == NULL)return true;/*NULL root*/ if(height(node->left) - height(node->right) > 1){ // if height of the left is larger with a diference greater than 1return false;} else if(height(node->right) - height(node->left) > 1){ // if the height of the right is larger with a difference greater than 1return false;} elsereturn true;} /** 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 << "|l_" << root -> element << "\n";} else {std::cout << "|r_" << root -> element << "\n";}}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;int level;regex integer ("[[:digit:]]+");std::string filename = argv[1];freopen(filename.c_str(), "r", stdin);std::string input;int data;while(std::cin >> input){if (input == "|l_" || input == "|r_"){std::cin>>data;inputs.push_back(input);values.push_back(data); } else if(input == "|"){level++; } else if(regex_match(input, integer)){data = stoi(input, nullptr, 10);inputs.push_back("root");values.push_back(data);} else if(input == "print"){print(root);std::cout << "\n";} else{std::cout<<"Data not consistent in file" << endl;return 0;}}data = 0;insert(data, root); if( balance(root) )std::cout << "true" << endl;elsestd::cout << "false" << endl;return 0;}/** END main method*/

Engineering

Computer Science

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