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