AVL Tree

there is an interactive demo here


video part1
video part2


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 

this will enable to rotate nodes.. like so 

current_node->left =  leftRotate(current_node->left);
current_node  = rightRotate(current_node);










you will then need to modify your InsertSubtree function so that it returns a TreeNode* instead of bool

you will no longer return true if the insert happens you will return a node in the tree
(each of the scenarios below tell you what to return)


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 
return InsertSubtree(root, 123)
becomes 
root = InsertSubtree(root, 123 )
or 

return  InsertSubtree(node->left, 123)
becomes 
node->left = InsertSubtree(node->left,123);



this will afford you the posibility of rotating the nodes inside the insert function 



the modified logic for  insert will be 

        // if current_node is nullptr insert here
        // set current_node to new TreeNode *
        // return current_node

        // if the current_node contains the value we are supposed to insert
        // simply return current_node, nothing else


        // we need to call insert for either the left or right side of the subtree
        //  so do you insert to the left or right?
        if (elem < subtree->data)
        {
            subtree->left  = insertSubtreeAVL(subtree->left, elem);
        }
        else
        {
            subtree->right = insertSubtreeAVL(subtree->right, elem);
        }



        // so now we need to balance the tree
        // create a couple int variables left_height and right_height
        // use the height function to set left_height and right_height by passing in the right and left pointer
				


        // LL scenario
        // cout "TestLL"
        // the left_height > right_height+1  
        // 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
        // cout "TestLR"
        // the left_height > right_height+1 
        // 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
        // cout "TestRR"
        // the right_height > left_height+1 
        // 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
        // cout "TestRL"
        // the right_height > left_height+1 
        // 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
	
        // last line of the function
		// return current_node , if none of the 4 scenarios where used



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 
or use the values below

testRR
i50i40i60i55i35i70i80d35i65px

testRL
i50i40i60i35i70i55i58d35i52px

testLL
i50i60i25i65i30i20i15d65i22px

testLR
i50i60i25i65i30i20i27d65i33px


all of these files needs to produce a FULL and BALANCED tree

take the output and paste it into the viewtree page so that you can see if tree is full and balanced.