Learning Objectives By 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?
Announcements
- Midterm 2 on Thursday
- Return Quizzes
- Collect Lab 7
- Lab 8 assigned
- Project Report 3 (one per group) and Peer Evaluation (each person to submit) due Thursday.
- Last day to drop with a "W" is this Friday
Review Activity - What is the max heap property?
- Trace build heap on the following values: 10, 6, 4, 9, 12, 5, 3
- Trace heap insert on the heap created above and the value 15.
Heap-Sort - Exchange the right most bottom key with the root
- Rebuild the Heap
- Repeat

Heap-Sort HeapSort(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 property
Big O Run-Time: O(n log n)
Group Activity: Heap Sort Practice - Take out your heap handout from last class and try the heap-sort algorithm question with a partner.
AVL Trees - An AVL tree (Georgy Adelson-Velsky and Evgenii Landis tree) is a self-balancing BST.
AVL Tree Property - Requires that the heights of the left and right children of every node differ by at most one.
|left.height - right.height| <= 1
- Maintains 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 Insert - We 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){} }; - Call BST insert
- Rebalance the Tree
- To 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 insertion
if (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->height
if (balance > 1 || balance < -1)
//re-balance the tree using rotations
//to be filled in later in class
Rotations 
- 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
 Right Rotation Pseudocode
Nodeptr Right_Rotate(Nodeptr root)
Nodeptr newRoot = root->left
root->left = newRoot->right
newRoot->right = root
root->height = maxHeight(root->left, root->right) + 1
newRoot->height = maxHeight(newRoot->left, newRoot->right) + 1
return newRoot Left Rotation
Before Left Rotation After Left Rotation
Example Left Rotation 
Activity 14.1: Left Rotation Pseudocode- Now write the pseudocode for left rotation.
- Use the images and the right rotation pseudocode to help yourself.
Activity 14.2: Single Rotation Practice
- Trace the following AVL insertions:
- Example 1: Insert 1, 2, 3
- Example 2: Insert 2, 1, 4, 6, 3, 5
- Example 3: Insert 2, 1, 4, 6, 7
- Example 4: Insert 2, 1, 4, 3, 6, 7
Double Rotations - Sometimes 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 right
- If the right subtree is "left heavy" (i.e. left.height - right.height > 1)
- rotate right then rotate left
- In 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)
 Double Rotation Videos
Activity 14.3: Double Rotation Practice
- Trace the following AVL insertions:
- When 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 Solution
Image source
Wrap Up- With your partner, answer the learning objective questions from the beginning of the lesson.
Upcoming Assignments - Lab 8 due one week from today
|