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 HeapRepeat Heap-SortHeapSort(A)    n = length(A)    for (i = n down to 2)        A <--> 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 classRotations With 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 Examples Image source.Right Rotation        Before Rotation        After Rotation  Note 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 Rotation Image 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 RotationExample Left Rotation Image 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 rotation Image 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 rotation Image 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;