## Binary Search Tree

you will create an AVL Tree and a menu driven main files copy all the files provided for you copy over your BST.h and your main1.cpp file from your BST homework over from your tested and fully functional BST homework do a search and replace in your main and BST.h replace BST with AVL rename BST.h to AVL.h you will then need to add the following functions to your AVL class you will then need to modify your InsertSubtree function so that it returns a Node * EVERY SINGLE TIME you call InsertSubtree you will need to set the node * that you used as a parameter to the value the funtion returns. ie root = InsertSubtree(root, 123 ) or node->left = InsertSubtree(node->left, 123) this will afford you the posibility of rotating the nodes inside the insert function The insert will be very similar to the BST insert but dont return ANYTHING or leave the function after an insert, the only return will be at then end of one of the below 4 senarios after you have made the changes to the return type and have tested that is is working properly add in the following logic to balance the tree AFTER your existing insert logic // so now we need to balance the tree // create a couple bool variables left_taller and right_taller // use the height function to calculate if the right or left // side of the current node is taller // they are true if the difference in height is more than 1 // LL scenario // the left side is taller AND the value that was just added is // smaller than the value in the left child node // action: // rotate the current node to the right // return the current node // LR scenario // the left side is taller AND the value just added is // larger than the value in the left child node // action: // rotate left child node to the left // then rotate the current node to the right // return the current node // RR scenario // the right side is taller AND the value that was just added is // larger than the value in the right child node // action: // rotate the current node to the left // return the current node // RL scenario // the right side is taller AND the value just added is // less than the value in the right child node // action: // rotate right child node to the right // then rotate the current node to the left // return the current node the output when testing should match that of the runable examples there are 4 int type testfiles in the lab directory that are designed specifically to test the AVL funcionality testRR i50i40i60i55i35i70i80d35i65px testRL i50i40i60i35i70i55i58d35i52px testLL i50i60i25i65i30i20i15d65i22px testLR i50i60i25i65i30i20i27d65i33px all of these files needs to produce a FULL and BALANCED tree