C++ Programming Language

For this assignment, you are to implement the AVL Tree, given a complete implementation of the BST Tree(found in MyCourses). You are required to implement the algorithms listed on the next page and modify the Insert/Delete code to use these algorithms properly. Some hints: 1. Implement Get Height and Balance Factor first and test it. 2. Implement the Left Single and Right Single next, and then implement the Balance Tree function to only perform single rotations. Test your progress in your own test code. 3. Then implement the double rotations by calling the single rotations properly. Complete the Balance Tree after coding the double rotations and test it in your own test code. 4. Finally, use the test code I provided to ensure the tree is balancing properly.

Get Height Arguments node: Pointer to node Return Type:Integer Description: Recursively decides the height of a subtree formed by the argument node. Pseudocode 1. If the node doesnt exist a. Return -1 2. Else a. Return 1 + max(GetHeight(nodes left), GetHeight(nodes right))

Balance Factor Arguments node: Pointer to node Return Type Integer Description Called Getheight on the left node and right node, and subtracts the right nodes height from the left nodes height Pseudocode 1. Return GetHeight(nodes left) - GetHeight(nodes right)

Right Single Rotate Arguments node: Pointer Reference to node Return Type None Description Performs a Right single rotate on a left heavy tree Pseudocode 1. Assign a temporary variable to nodes lefts right child. 2. Set nodes lefts right to point to node. 3. Point node to nodes left 4. Point nodes rights left to the temporary variable

Left Single Rotate Arguments node: Pointer Reference to node Return Type None Description Performs a Left single rotate on a right heavy tree Pseudocode 1. Assign a temporary variable to nodes rights left child. 2. Set nodes rights left to point to node. 3. Point node to nodes right 4. Point nodes lefts right to the temporary variable

Left Right Rotate Arguments node: Pointer Reference to node Return Type None Description Performs a double rotation on a node in the tree Pseudocode 1. Call Left Single Rotate on tmps left node 2. Call Left Single Rotate on tmp

Right Left Rotate Arguments node: Pointer Reference to node Return Type None Description Performs a double rotation on a node in the tree Pseudocode 1. Call Right Single Rotate on tmps right node 2. Call Left Single Rotate on tmp

Balance Tree Arguments node: Pointer Reference to node Return Type None Description Balance Factor determines if a node and its children need to be rotated, and if so what rotation should occur. Balance Factor is called in Insert and Delete methods. Pseudocode 1. Get the balance Factor of the Node 2. If the node doesnt need balancing: a. Return and do nothing 3. Else a. If the tree is left heavy: i. If temps left child has a left child 1. Perform a right single rotation ii. Else 1. Perform a Left Right rotation b. If the tree is right heavy: i. If temps right child has a right child 1. Perform a left single rotation ii. Else 1. Perform a Right Left rotatio

Test file:

#include "AVL.h" #include  bool testAVLArray(int *testArr, int tSize, int *AVL, int aSize); int main() { AVL a1; int count = 0; bool result = false; //*********************Test 1***** a1.Insert(52); a1.Insert(44); a1.Insert(37); int size = 0; int *pre = a1.PreOrderToArray(size); int test1[] = { 44, 37, 52 }; result = testAVLArray(test1, 3, pre, size); cout   int max(int a, int b) return (a > b) a : b; ese functions should be co code. ted into the Class definition so int count -0; return count; void recursePreorderCountTreeNodes (Node n, int &count) if (n = NULL) returnj else count++; recursePreOrderCountTreeNodes (n->left, count); recursePreorderCountTreeNodes (n->right, count); //This is a naive way to do this, but we're just testing... int preordernew int[numNodes]; int index recursePreorderToArray(root, preorder, index); return preorder; void recursePreorderToArray (Node n, int & arr, int &index) if (n = NULL) return; else arr[index++] n->data; ToArray(n-left, arr, index); ToArray(n-right, arr, index)5 =  int max(int a, int b) return (a > b) a : b; ese functions should be co code. ted into the Class definition so int count -0; return count; void recursePreorderCountTreeNodes (Node n, int &count) if (n = NULL) returnj else count++; recursePreOrderCountTreeNodes (n->left, count); recursePreorderCountTreeNodes (n->right, count); //This is a naive way to do this, but we're just testing... int preordernew int[numNodes]; int index recursePreorderToArray(root, preorder, index); return preorder; void recursePreorderToArray (Node n, int & arr, int &index) if (n = NULL) return; else arr[index++] n->data; ToArray(n-left, arr, index); ToArray(n-right, arr, index)5 =