# AVL Trees --- ## Objectives 1. Understand and analyze balance in Binary Search Trees 2. Understand AVL Trees and their self-balancing properties 3. Implement and analyze AVL Tree operations 4. Compare performance between regular BST and AVL --- ## Binary Search Trees: A Quick Review - BST Property: For any node N - All values in left subtree < N.value - All values in right subtree > N.value - Operations: - Search: O(h) where h is height - Insert: O(h) - Delete: O(h) --- ## The Problem: Unbalanced Trees ``` Balanced BST (h = log n): Unbalanced BST (h = n): 50 10 / \ \ 30 70 20 / \ \ \ 20 40 80 30 \ ... \ n ``` - Balanced: Operations take O(log n) time - Unbalanced: Operations degrade to O(n) time --- ## Real-world Impact of Unbalanced Trees | n = 1,000,000 | Balanced Tree | Unbalanced Tree | |---------------|---------------|-----------------| | Height | ~20 | 1,000,000 | | Search time | ~20 steps | Up to 1M steps | **Example:** Database index performance can drop from milliseconds to seconds --- ## AVL Tree Solution - Named after inventors: **A**delson-**V**elsky and **L**andis (1962) - First self-balancing binary search tree - Guarantees O(log n) operations by maintaining balance **Key Property:** For any node, heights of left and right subtrees differ by at most 1 --- ### Height and Balance Factor 1. _Height of a Node_: - Height of leaf node = 1 - Height of null (empty tree) = 0 - For other nodes: max(left.height, right.height) + 1 2. _Balance Factor_: - BF = Height(Left) - Height(Right) - AVL property: BF must be -1, 0, or 1 Example: ~.~ ``` A(h=3) A(BF=0) / \ / \ B(h=2) C(h=2) B(BF=0) C(BF=1) / \ \ / \ \ D(h=1) E(h=1) F(h=1) D(BF=0) E(BF=0) F(BF=0) ``` --- ### Balance Factor Calculation - BF = Height(Left Subtree) - Height(Right Subtree) - AVL property: BF must be -1, 0, or 1 Example: ``` A / \ B C / \ D E Heights: D,E: 1 (leaves) B: 2 (max(0,-1) + 1) C: 2 (max(0,1) + 1) A: 3 (max(2,2) + 1) Balance Factors: D: (0)-(0) = 0 // Leaf node: both subtrees are null/empty (0) E: (0)-(0) = 0 // Leaf node: both subtrees are null (0) B: 1-(0) = 1 // Left child height 1, no right child (0) C: (0)-1 = -1 // No left child (0), right child height 1 A: 2-2 = 0 // Both subtrees height 2 ``` *Exercise:* Calculate height and BF for each node --- ## AVL Insertion Process 1. Insert node using standard BST insertion 2. Update heights of all nodes on path from insertion point to root 3. Check balance factor at each ancestor node 4. If any node becomes unbalanced (|BF| > 1), perform rotation --- ## When Balance is Disrupted After BST insertion, an AVL tree might become unbalanced in 4 ways: 1. **Left-Left (LL) Case**: Insertion into left subtree of left child 2. **Right-Right (RR) Case**: Insertion into right subtree of right child 3. **Left-Right (LR) Case**: Insertion into right subtree of left child 4. **Right-Left (RL) Case**: Insertion into left subtree of right child When a new node is inserted, it may cause the AVL property to be violated at some ancestor node. An ancestor becomes unbalanced (BF < -1 or BF > 1) in one of four ways: --- ### 1. Left-Left Imbalance - Occurs when a node is inserted into the left subtree of the left child - Results in Balance Factor > 1 at ancestor ``` Example: Insert 10 causes Left-Left imbalance at 30 Before: After Insert: 30 30 (BF=2) / / 20 → 20 (BF=1) / 10 ``` --- ### 2. Right-Right Imbalance - Occurs when a node is inserted into the right subtree of the right child - Results in Balance Factor < -1 at ancestor ``` Example: Insert 30 causes Right-Right imbalance at 10 Before: After Insert: 10 10 (BF=-2) \ \ 20 → 20 (BF=-1) \ 30 ``` --- ### 3. Left-Right Imbalance - Occurs when a node is inserted into the right subtree of the left child - Results in Balance Factor > 1 at ancestor ``` Example: Insert 25 causes Left-Right imbalance at 30 Before: After Insert: 30 30 (BF=2) / / 20 → 20 (BF=-1) \ 25 ``` --- ### 4. Right-Left Imbalance - Occurs when a node is inserted into the left subtree of the right child - Results in Balance Factor < -1 at ancestor ``` Example: Insert 25 causes Right-Left imbalance at 20 Before: After Insert: 20 20 (BF=-2) \ \ 30 → 30 (BF=1) / 25 ``` --- ### How to Identify Imbalance Type: 1. Find the first unbalanced ancestor (|BF| > 1) 2. Look at the path that caused imbalance: - Left-Left: left-left path to new node - Right-Right: right-right path to new node - Left-Right: left-right path to new node - Right-Left: right-left path to new node ``` Example: Analyzing the path A(BF=2) / B(BF=1) / C ← new node Path from A to C is: left->left Therefore: Left-Left imbalance ``` --- ## Understanding Rotation Types Balance is restored through rotations. Type depends on insertion path: 1. LL (Left-Left): Inserted into left subtree of left child 2. RR (Right-Right): Inserted into right subtree of right child 3. LR (Left-Right): Inserted into right subtree of left child 4. RL (Right-Left): Inserted into left subtree of right child --- ## Left-Left (LL) Case - Occurs when: Node inserted in left subtree of left child - Fix: Single right rotation ``` Before Insertion: After Insert 10: After Rotation: 30 30 20 / / / \ 20 → 20 → 10 30 / 10 Process: 1. 30 becomes unbalanced (BF=2) 2. Insertion path: left->left 3. Single right rotation fixes it ``` --- ## Right-Right (RR) Case - Occurs when: Node inserted in right subtree of right child - Fix: Single left rotation ``` Before Insertion: After Insert 30: After Rotation: 10 10 20 \ \ / \ 20 → 20 → 10 30 \ 30 Process: 1. 10 becomes unbalanced (BF=-2) 2. Insertion path: right->right 3. Single left rotation fixes it ``` --- ## Left-Right (LR) Case - Occurs when: Node inserted in right subtree of left child - Fix: Double rotation (left then right) ``` Before Insertion: After Insert 25: After Left: After Right: 30 30 30 25 / / / / \ 20 → 20 → 25 → 20 30 \ / 25 20 Process: 1. 30 becomes unbalanced (BF=2) 2. Insertion path: left->right 3. Need two rotations to fix ``` --- ## Right-Left (RL) Case - Occurs when: Node inserted in left subtree of right child - Fix: Double rotation (right then left) ``` Before Insertion: After Insert 25: After Right: After Left: 20 20 20 25 \ \ \ / \ 30 → 30 → 25 → 20 30 / \ 25 30 Process: 1. 20 becomes unbalanced (BF=-2) 2. Insertion path: right->left 3. Need two rotations to fix ``` --- ## Complete Insertion Process 1. Perform standard BST insertion 2. Update heights of affected nodes 3. Check balance factor at each ancestor 4. If unbalance found, determine case type: - Check insertion path (LL, RR, LR, RL) - Perform appropriate rotation(s) --- ## AVL Insertion: Full Example Insert 10, 20, 30, 40, 50 into an empty AVL tree: ``` Insert 10: 10 Insert 20: 10 → 10 \ \ 20 20 Insert 30: 10(3,-2) RR → Single left Rotation 20 \ / \ 20(2,-1) 10 30 \ 30(1,0) Insert 40: 20(3,-1) → 20 / \ / \ 10(1,0) 30(2,-1) 10 30 \ \ 40(1,0) 40 Insert 50: 20(4) RR → Single Left Rotation 20(3,-1) / \ / \ 10(1,0) 30(3,-2) 10(1,0) 40(2,0) \ / \ 40(2,-1) 30(1,0) 50(1,0) \ 50(1,0) ``` https://www.cs.usfca.edu/~galles/visualization/AVLtree.html --- ## AVL vs. Regular BST: Code Comparison **Regular BST Insert:** ```java Node insert(Node root, int key) { if (root == null) return new Node(key); if (key < root.key) root.left = insert(root.left, key); else if (key > root.key) root.right = insert(root.right, key); return root; } ``` **AVL Insert:** ```java Node insert(Node root, int key) { // Standard BST insert if (root == null) return new Node(key); if (key < root.key) root.left = insert(root.left, key); else if (key > root.key) root.right = insert(root.right, key); // Update height root.height = 1 + Math.max(height(root.left), height(root.right)); // Get balance factor int balance = getBalance(root); // If unbalanced, perform rotations // (LL, RR, LR, RL cases) return root; } ``` --- ## AVL Tree Operations: Time Complexity | Operation | AVL Tree | Unbalanced BST | |---------------|----------------|-----------------| | Search | O(log n) | O(n) worst case | | Insert | O(log n) | O(n) worst case | | Delete | O(log n) | O(n) worst case | --- ## AVL Deletion: Overview 1. Perform standard BST deletion 2. Update height of current node 3. Check balance factor of current node 4. If unbalanced, perform appropriate rotation 5. Repeat for all ancestors up to root --- ## AVL Tree Implementation Tips 1. Store height directly in nodes (faster than recalculating) 2. Update heights bottom-up during rebalancing 3. Use recursion for clearer code 4. Check balance after each modification **Exercise:** Complete the rotation implementations --- ## Knowledge Check http://quiz.codewitme.com ### labs