--- title: "AVL rotations with examples" subject: "Data Structure and Algorithm" chapter: 6 key: "semester_4/data_structure_and_algorithm:avl-rotations" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-rotations site: BCT Engineering --- # AVL rotations with examples Data Structure and Algorithm · Chapter 6: Trees - Asked in: 2074 Bhadra, 6 marks - Video: [AVL Trees Simply Explained](https://www.youtube.com/watch?v=zP2xbKerIds) — Maaneth De Silva - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-rotations - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6 ## Question Discuss about AVL rotations with suitable examples. ## Short answer When an AVL node's balance factor becomes ±2, rotations restore balance: LL case requires a right rotation; RR requires a left rotation; LR uses left rotation on left child then right rotation; RL uses right rotation on right child then left rotation. Example: inserting 30,20,10 creates LL imbalance fixed by right rotation at 30. ## Answer An **AVL tree** is a height-balanced BST where, for every node, the heights of the left and right subtrees differ by at most 1. When an insertion or deletion breaks this (balance factor becomes +2 or −2), the tree is repaired by **rotations**. There are four cases, in two groups. #### 1. Single rotations **LL case → right rotation.** New node goes into the left subtree of the left child. ```text Insert 30, 20, 10: 30 (bf +2) 20 / / \ 20 ==> 10 30 / 10 ``` The left child 20 becomes the root, 30 becomes its right child (20's old right subtree, if any, becomes 30's left subtree). **RR case → left rotation.** New node goes into the right subtree of the right child. ```text Insert 10, 20, 30: 10 (bf -2) 20 \ / \ 20 ==> 10 30 \ 30 ``` #### 2. Double rotations **LR case → left rotation on the left child, then right rotation on the root.** ```text Insert 30, 10, 20: 30 30 20 / / / \ 10 ==> 20 ==> 10 30 \ / 20 10 (left at 10) (right at 30) ``` **RL case → right rotation on the right child, then left rotation on the root.** ```text Insert 10, 30, 20: 10 10 20 \ \ / \ 30 ==> 20 ==> 10 30 / \ 20 30 (right at 30) (left at 10) ``` #### Summary | Case | Imbalance | Rotation | |---|---|---| | LL | bf = +2, left child bf ≥ 0 | right | | RR | bf = −2, right child bf ≤ 0 | left | | LR | bf = +2, left child bf = −1 | left, then right | | RL | bf = −2, right child bf = +1 | right, then left | Each rotation takes O(1) time and keeps the in-order sequence unchanged, so the tree is still a valid BST. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which rotation fixes the LL case (insert 30, 20, 10)? A. Single right rotation B. Single left rotation C. Left rotation then right rotation D. Right rotation then left rotation Answer: A. The new node is in the left subtree of the left child, so the left child (20) is rotated up with a right rotation. (Key point: LL case) 2. For inserts 10, 20, 30 the balance factor at 10 is -2. What fixes it? A. Right rotation at 10 B. Left rotation at 10, making 20 the root C. Left then right rotation D. No rotation is needed Answer: B. A right-heavy chain (RR case) needs a single left rotation. (Key point: RR case) 3. How is the LR case fixed? A. Right rotation on the left child, then left rotation on the root B. A single right rotation C. Left rotation on the left child, then right rotation on the root D. A single left rotation Answer: C. A zig-zag shape needs a double rotation: first straighten the child, then rotate the root. (Key point: LR case) 4. How is the RL case fixed? A. Left rotation on the right child, then right rotation on the root B. A single left rotation C. Two right rotations D. Right rotation on the right child, then left rotation on the root Answer: D. RL is the mirror of LR. (Key point: RL case)