Heaps and AVL Trees in CS Lecture 15

CS 133, Spring 2023 Lecture 15: heaps; AVL trees Thank you to Marty Stepp and Stuart Reges for parts of these slides

Heaps heap: A complete binary tree with vertical ordering. complete tree: Every level is full except possibly the lowest level, which must be filled from left to right (i.e., a node may not have any children until all possible siblings exist) 2

Heap height and runtime The height of a complete tree is always log N. How do we know this for sure? Because of this, if we implement a priority queue using a heap, we can provide the following runtime guarantees: add: O(log N) peek: O(1) remove: O(log N) n-node complete tree of height h: 2h n 2h+1 1 h = log n 3

The push operation When an element is added to a heap, where should it go? Must insert a new node while maintaining heap properties. queue.push(15); new node 10 15 20 80 40 60 85 99 50 700 65 4

The remove operation When the root is removed from a heap, it should be initially replaced by the rightmost leaf (to maintain completeness). But the heap ordering property becomes broken! 10 65 20 80 20 80 40 60 85 99 40 60 85 99 700 50 65 700 50 65 5

Implementation of a heap Often, in the real world, when implementing a complete binary tree, we actually "cheat" and just use an array index of root = 1 (leave 0 empty for simplicity) for any node n at index i, index of n.left = 2i index of n.right = 2i + 1 parent index? 6 6

Trees and balance balanced tree: One where for every node R, the height of R's subtrees differ by at most 1, and R's subtrees are also balanced. Runtime of add / remove / contains are closely related to height. Balanced tree's height is roughly log2N. Unbalanced is closer to N. root 19 root 14 9 11 9 6 14 7 4 8 19 6 height = 4 (balanced) height = 7 (unbalanced) 7 4 7

BST balance question Adding the following nodes to an empty BST in the following order produces the tree at right: 22, 9, 34, 18, 3. 22 Q: What is an order in which we could have added the nodes to produce an unbalanced tree? A. 18, 9, 34, 3, 22 B. 9, 18, 3, 34, 22 C. 9, 22, 3, 18, 34 D. none of the above 34 9 18 3 8

AVL trees AVL tree: A binary search tree that uses modified push and pop operations to stay balanced as its elements change. basic idea: When nodes are added/removed, repair tree shape until balance is restored. rebalancing is O(1); overall tree maintains an O(log N) height 8 25 rotate 8 3 25 3 11 11 9

Balance factor balance factor, for a tree node T : BF(T) = height(T->right) - height(T->left) (the tree at right shows BF of each node) -2 3 1 an AVL tree maintains a "balance factor" in each node of 0, 1, or -1 -2 0 -1 0 10

Which are balanced? What is the balance factor of each tree node? 14 5 4 9 28 2 7 2 5 9 6 31 -1 4 8 4 20 44 -2 3 3 3 0 15 22 -4 1 11 33 11

AVL push operation For all AVL operations, we assume the tree was balanced before the operation began. Adding a new node begins the same as with a typical BST, traversing left and right to find the proper location and attaching the new node. But adding this new node may unbalance the tree by 1: 55 set.add(49); 29 87 -3 42 49 12

AVL push cases Consider the lowest node k2 that has now become unbalanced. The new offending node could be in one of the four following grandchild subtrees, relative to k2: 1) Left-Left, 2) Left-Right, 3) Right-Left, 4) Right-Right 13

Key idea: rotations If a node has become out of balanced in a given direction, rotate it in the opposite direction. rotation: A swap between parent and left or right child, maintaining proper BST ordering. 8 25 rotate right 8 3 25 3 11 11 14

Types of AVL rotations R: fixes LL imbalance L: fixes RR imbalance LR: fixes LR imbalance RL: fixes RL imbalance 15

Right rotation right rotation (clockwise): left child k1 becomes parent original parent k2 demoted to right k1's original right subtree B (if any) is attached to k2 as left subtree (fixes Case 1 (LL)) 16

Right rotation example What is the balance factor of k2 before and after rotating? 17

Right rotation steps 1. Detach left child (11)'s right subtree (27) (don't lose it!) 2. Consider left child (11) be the new parent. 3. Attach old parent (43) onto right of new parent (11). 4. Attach new parent (11)'s old right subtree (27) as left subtree of old parent (43). 43 43 11 11 11 65 65 8 43 8 8 27 27 3 27 65 3 3 18

Right rotation code void rightRotate(TreeNode*& oldParent) { // 1. detach left child's right subtree TreeNode* orphan = oldParent->left->right; // 2. consider left child to be the new parent TreeNode* newParent = oldParent->left; // 3. attach old parent onto right of new parent newParent->right = oldParent; // 4. attach new parent's old right subtree as // left subtree of old parent oldParent->left = orphan; oldParent->height = height(oldParent); // update nodes' newParent->height = height(newParent); // height values oldParent = newParent; } 19

Right rotation code int height(TreeNode* node) { if (node == nullptr) { return 0; } int left = (node->left == nullptr)? 0 : node->left->height; int right = (node->right == nullptr)? 0 : node->right->height; return max(left, right) + 1; } 20

Left rotation left rotation (counter-clockwise): right child k2 becomes parent original parent k1 demoted to left k2's original left subtree B (if any) is attached to k1 as left subtree (fixes Case 4 (RR)) 21

Left rotation steps 1. Detach right child (65)'s left subtree (51) (don't lose it!) 2. Consider right child (65) be the new parent. 3. Attach old parent (43) onto left of new parent (65). 4. Attach new parent (65)'s old left subtree (51) as right subtree of old parent (43). 43 43 65 65 21 65 21 43 87 87 51 87 51 21 51 73 73 73 22

Left rotation code void leftRotate(TreeNode*& oldParent) { // 1. detach right child's left subtree TreeNode* orphan = oldParent->right->left; // 2. consider right child to be the new parent TreeNode* newParent = oldParent->right; // 3. attach old parent onto left of new parent newParent->left = oldParent; // 4. attach new parent's old left subtree as // right subtree of old parent oldParent->right = orphan; oldParent->height = height(oldParent); // update nodes' newParent->height = height(newParent); // height values oldParent = newParent; } 23

Problem cases A single right rotation does not fix Case 2 (LR). (Similarly, a single left rotation does not fix Case 3 (RL).) 24

Left-right double rotation left-right double rotation: (fixes Case 2 (LR)) 1) left-rotate k3's left child ... reduces Case 2 into Case 1 2) right-rotate k3 to fix Case 1 25

Left-right rotation example What is the balance factor of k1, k2, k3 before and after rotating? 26

Right-left double rotation right-left double rotation: (fixes Case 3 (RL)) 1) right-rotate k1's right child ... reduces Case 3 into Case 4 2) left-rotate k1 to fix Case 4 27

AVL add example Draw the AVL tree that would result if the following numbers were added in this order to an initially empty tree: 20, 45, 90, 70, 10, 40, 35, 30, 99, 60, 50, 80 45 20 70 60 90 35 10 30 40 50 80 99 28

Implementing add Perform normal BST add. But as recursive calls return, update each node's height from new leaf back up to root. If a node's balance factor becomes +/- 2, rotate to rebalance it. How do you know which of the four Cases you are in? Current node BF < -1 Case 1 (LL) or 2 (LR). look at current node's left child BF. left child BF < 0 Case 1 left child BF > 0 Case 2 Current node BF > 1 Case 3 (RL) or 4 (RR). look at current node's right child BF. right child BF < 0 Case 3 (fix with RL rotations) right child BF > 0 Case 4 (fix with L rotation) (fix with R rotation) (fix with LR rotations) 29

AVL remove Removing from an AVL tree can also unbalance the tree. Similar cases as with adding: LL, LR, RL, RR Can be handled with the same remedies: rotate R, LR, RL, L set.pop(8); 11 11 8 43 43 27 65 27 65 30

Remove extra cases AVL remove has 2 more cases beyond the 4 from adding: In these cases, the offending subtree has a balance factor of 0. (The cause of imbalance is both LL and LR relative to k1 below.) When an add makes a node imbalanced, the child on the imbalanced side always has a balance factor of either -1 or 1. After removing from subtree C: k1 k1 k2 k2 C C A B A B 31

Labeling the extra cases Let's label these two new cases of remove imbalance: Case 5: Problem is in both the LL and LR subtrees of the parent. Case 6: Problem is in both the RL and RR subtrees of the parent. Case 5 (After removing from subtree C) Case 6 (After removing from subtree A) k1 k1 k2 k2 C A A B B C 32

Fixing remove cases Each of these new cases can be fixed through a single rotation: To fix Case 5, we right rotate (shown below) To fix Case 6, we left rotate (symmetric case) Case 5 (After removing from subtree C) k2 Right rotate to fix imbalance: k1 k1 k2 C A C A B B 33

Implementing remove Perform normal BST remove. But as recursive calls return, update each node's height from new leaf back up to root. If a node's balance factor becomes +/- 2, rotate to rebalance it. Current node BF < -1 Case 1 (LL) or 2 (LR) or 5 (L-both). look at current node's left child BF. left child BF < 0 Case 1 left child BF > 0 Case 2 left child BF = 0 Case 5 Current node BF > 1 Case 3 (RL) or 4 (RR) or 6 (R-both). look at current node's right child BF. right child BF < 0 Case 3 (fix with RL rotations) right child BF > 0 Case 4 (fix with L rotation) right child BF = 0 Case 6 (fix with L rotation) (fix with R rotation) (fix with LR rotations) (fix with R rotation) 34

AVL remove example Suppose we start with the AVL tree below. Draw the AVL tree that would result if the following numbers were removed in this order from the tree: 10, 30, 40, 35, 70, 90, 99 45 50 20 45 80 70 60 60 90 35 10 30 40 50 80 99 35

How efficient is AVL? An AVL tree has the same general operations as a BST, with rebalancing added to the add/remove operations. How much time does it take to rebalance the tree? How much time does it take to rebalance one node? How many nodes at most will we need to rebalance per add/remove? add: O(log N) to walk down the tree and add the element; O(log N) number of nodes' heights to update; O(1) single node may need to be rotated. O(log N) overall. contains: Unmodified. O(log N). remove: O(log N) to walk down the tree and remove the element; O(log N) number of nodes' heights to update; O(1) single node may need to be rotated. O(log N) overall. 36