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.