Welcome to Lesson 14!Learning ObjectivesBy the end of this class, you should know...What is an AVL Tree?What is the definition of a balanced tree according to the AVL tree property?How do AVL trees maintain their balance?What is a simple left rotation and when do you use it?What is a simple right rotation and when do you use it?How do you write the pseudocode for simple left and right rotations?What is a double rotation?What is a left-right rotation and when do you use it?What is a right-left rotation and when do you use it?AnnouncementsMidterm 2 on ThursdayReturn QuizzesCollect Lab 7Lab 8 assignedProject Report 3 (one per group) and Peer Evaluation (each person to submit) due Thursday.Last day to drop with a "W" is this FridayReview ActivityWhat is the max heap property?Trace build heap on the following values: 10, 6, 4, 9, 12, 5, 3Trace heap insert on the heap created above and the value 15.Heap-SortExchange the right most bottom key with the rootRebuild the HeapRepeatHeap-SortHeapSort(A)    n = length(A)    for (i = n down to 2)        A[1] <--> A[i] //swap        Heap_size(A)-- //consider your heap to be one smaller        Max-Heapify(A,1) //restore max heap propertyBig O Run-Time: O(n log n)Group Activity: Heap Sort PracticeTake out your heap handout from last class and try the heap-sort algorithm question with a partner.AVL TreesAn AVL tree (Georgy Adelson-Velsky and Evgenii Landis tree) is a self-balancing BST.AVL Tree PropertyRequires that the heights of the left and right children of every node differ by at most one.|left.height - right.height| <= 1Maintains a balanced tree to achieve O(log n) time for ALL operations.Review: What is the Big-O runtime of BST operations in best, worst and average cases?AVL Tree InsertWe need to insert nodes in such a way that the AVL tree property is satisfied.Thus, inside of our BST Nodes we are going to keep track of the height of the nodes.struct Node{    bstdata data;    int height;    Node* left;    Node* right;    Node(): left(NULL), right(NULL), height(0){}    Node(bstdata newdata): left(NULL), right(NULL), data(newdata), height(0){}};Insertion has 2 steps:Call BST insertRebalance the TreeTo balance the tree we use what are called "rotations" to alter the location of certain nodes.AVL Insert Pseudocode (Partial)Node avlInsert(Node root, int value)    //BST style insertionif (root == NULL)    return new Node(value)else if(root.data >= value)    root->left = avlInsert(root->left, value)else    root->right = avlInsert(root->right, value)//value has now been inserted//Is the resulting tree unbalanced?int balance = root->left->height - root->right->heightif (balance > 1 || balance < -1)    //re-balance the tree using rotations    //to be filled in later in classRotationsWith rotations, we want the height of the tree to become shorter (tree looks less like a linked list)Important: These rotations maintain the order of the BST: T1 < A < T2 < B < T3.Simple ExamplesImage source.Right Rotation        Before Rotation        After RotationNote that the upper case letters represent nodes in the tree, while the lower case letters represent possible subtrees.What happened to subtree c during the rotation?Example Right RotationImage source.Right Rotation PseudocodeNodeptr Right_Rotate(Nodeptr root)Nodeptr newRoot = root->leftroot->left = newRoot->rightnewRoot->right = rootroot->height = maxHeight(root->left, root->right) + 1newRoot->height = maxHeight(newRoot->left, newRoot->right) + 1return newRoot Left Rotation                      Before Left Rotation                               After Left Rotation Example Left RotationImage source.Activity 14.1: Left Rotation PseudocodeNow write the pseudocode for left rotation.Use the images and the right rotation pseudocode to help yourself.Activity 14.2: Single Rotation PracticeTrace the following AVL insertions:Example 1: Insert 1, 2, 3Example 2: Insert 2, 1, 4, 6, 3, 5Example 3: Insert 2, 1, 4, 6, 7Example 4: Insert 2, 1, 4, 3, 6, 7Double RotationsSometimes a single rotation is not enough to balance a tree.Consider the following example:Our reaction might be to right rotate it, like so:However, we are now no better off than when we started.In cases like these (zig-zag pattern), we need to use a double rotation.We will need to do either a left-right rotation or a right-left rotation, depending on the situation.If the left subree is "right heavy" (i.e. left.height - right.height < -1)rotate left then rotate rightIf the right subtree is "left heavy" (i.e. left.height - right.height > 1)rotate right then rotate leftIn the example above, we have a left heavy right subtree.Therefore, we will do a left-right rotation.Step 1: Rotate left around the root.left, i.e. node A (to get a familar shape)Step 2: Rotate right around the root, i.e. B (to get a balanced tree)Example of left-right rotationImage source.If we have the opposite situation, where the right subtree is left heavy:Then, we must perform a right-left rotation.Step 1: Rotate right around root.right, i.e. A (to get a familar shape)Step 2: Rotate left around root, i.e. B (to get a balanced tree)Example of right-left rotationImage source.Double Rotation VideosPart 1Part 2Part 3Activity 14.3: Double Rotation PracticeTrace the following AVL insertions:3 2 1 4 5 6 7 16 15 14When you are finished, double check your work at the bottom.AVL Insert Pseudocode (Full)Nodeptr avlInsert(Nodeptr root, int value){    //BST style insertion    if (root == NULL)        return(newNode(value));     if (value < root.data)        root->left  = avlInsert(root->left, value);    else        root->right = avlInsert(root->right, value);     //Check the balance    int balance = height(root->left) - height(root->right);    //Check for 4 cases     // Simple Right Rotation    if (balance > 1 && value < root->left->data)        return rightRotate(root);     // Simple Left Rotation    else if (balance < -1 && value > root->right->data)        return leftRotate(root);     // Left Right Case    else if (balance > 1 && value > root->left->value)        root->left =  leftRotate(root->left);        return rightRotate(root);     // Right Left Case    else if (balance < -1 && value < root->right->data)        root->right = rightRotate(root->right);        return leftRotate(root);       //return the node pointer    return root;Double Insertion SolutionImage sourceWrap UpWith your partner, answer the learning objective questions from the beginning of the lesson.Upcoming AssignmentsLab 8 due one week from today