🌳 AVL Trees Study Guide

Self-Balancing Binary Search Trees

📚 Introduction to AVL Trees

What is an AVL Tree?

An AVL tree is a self-balancing binary search tree named after its inventors Adelson-Velsky and Landis. It maintains a balanced structure by ensuring that for every internal node, the heights of its two children differ by at most 1.

Key Property: For every internal node v, the heights of the children can differ by at most 1.

Mathematically: |height(left) - height(right)| ≤ 1

Why AVL Trees?

  • Guaranteed Performance: Operations are always O(log n)
  • No Worst Case: Unlike regular BST which can degrade to O(n)
  • Automatic Balancing: Self-adjusts after insertions and deletions
  • Efficient Searching: Maintains logarithmic height

🎯 AVL Tree Properties

Balance Factor

The balance factor of a node is calculated as:

Balance Factor = height(left subtree) - height(right subtree)

Valid balance factors: -1, 0, +1

  • +1: Left subtree is one level taller
  • 0: Both subtrees have equal height
  • -1: Right subtree is one level taller
  • +2 or -2: ⚠️ Tree is unbalanced! (needs rotation)

Height of AVL Tree

h < 2log(n) + 2

Therefore: h = O(log n)
Important Proof Concept:
Let n(h) = minimum number of nodes in an AVL tree of height h
• n(1) = 1
• n(2) = 2
• n(h) = 1 + n(h-1) + n(h-2)

Since n(h-1) > n(h-2), we get n(h) > 2n(h-2)
By induction: n(h) > 2^(h/2-1)
Taking logarithms: h < 2log n(h) + 2

🔄 Tree Rotations

Rotations are the fundamental operations used to restore balance in an AVL tree. There are 4 types of rotations based on the structure of imbalance.

When to Use Rotations?

  • When balance factor becomes +2 or -2
  • After insertion or deletion operations
  • To maintain the AVL property

1️⃣ Single Right Rotation (LL Case)

When: Left-Left imbalance (same sign)

Pattern: Left subtree is taller, and imbalance is in left child's left subtree

z (imbalanced)
↙
y
↙
x

⬇ Right Rotation

  y
↙ ↘
x   z

2️⃣ Single Left Rotation (RR Case)

When: Right-Right imbalance (same sign)

Pattern: Right subtree is taller, and imbalance is in right child's right subtree

z (imbalanced)
  ↘
  y
  ↘
  x

⬇ Left Rotation

  y
↙ ↘
z   x

3️⃣ Left-Right Rotation (LR Case)

When: Left-Right imbalance (opposite signs)

Pattern: Left subtree is taller, but imbalance is in left child's right subtree

z
↙
y
 ↘
 x

⬇ Left then Right

  x
↙ ↘
y   z

4️⃣ Right-Left Rotation (RL Case)

When: Right-Left imbalance (opposite signs)

Pattern: Right subtree is taller, but imbalance is in right child's left subtree

z
 ↘
 y
↙
x

⬇ Right then Left

  x
↙ ↘
z   y
💡 Quick Rule:
  • Same Sign (both left or both right) → Single Rotation
  • Opposite Signs (left-right or right-left) → Double Rotation

Trinode Restructuring

A general approach to handle all rotation cases:

  1. Let (a, b, c) be the inorder listing of nodes x, y, z
  2. Perform rotations to make b the topmost node
  3. a becomes the left child, c becomes the right child
  4. Subtrees T₀, T₁, T₂, T₃ are distributed appropriately

➕ Insertion in AVL Trees

Algorithm Steps

  1. Insert as in BST: Find the correct position and insert the new node
  2. Update Heights: Travel up from the inserted node, updating heights
  3. Check Balance: At each ancestor node, check the balance factor
  4. Perform Rotation: If unbalanced (|BF| = 2), perform appropriate rotation
  5. Continue Upward: Continue checking until root is reached

📝 Example: Inserting 54

Consider an AVL tree with nodes: 44, 17, 78, 32, 50, 88, 48, 62

After inserting 54:

  • Node 62 becomes unbalanced (balance factor = -2)
  • Pattern: Right-Left (RL case)
  • Solution: Right rotation at 62, then restructure
  • Result: Balanced tree with 54 in correct position
Key Insight: Only ONE rotation is needed for insertion! The rotation fixes all imbalances created by the insertion.

Complexity Analysis

Time Complexity: O(log n)
  • Finding insertion point: O(log n)
  • Updating heights: O(log n)
  • Single rotation: O(1)
  • Total: O(log n)

➖ Deletion in AVL Trees

Algorithm Steps

  1. Delete as in BST: Remove the node using standard BST deletion
  2. Start from Parent: Begin at the parent of the deleted node
  3. Update Heights: Recalculate heights going upward
  4. Check Balance: Check balance factor at each node
  5. Perform Rotations: If unbalanced, perform appropriate rotation
  6. Continue to Root: Must check ALL the way to the root
⚠️ Critical Difference from Insertion:
Deletion may require MULTIPLE rotations as you travel up to the root! Each rotation might create a new imbalance higher up.

📝 Example: Deleting 32

From a tree with nodes: 44, 17, 62, 32, 50, 78, 48, 54, 88

  1. Delete node 32 (leaf node)
  2. Parent 17 becomes unbalanced
  3. Perform rotation at 17
  4. Check parent nodes up to root
  5. Perform additional rotations if needed

BST Deletion Cases

  • Case 1: Node has no children (leaf) → Simply remove
  • Case 2: Node has one child → Replace node with its child
  • Case 3: Node has two children → Replace with inorder successor/predecessor

Complexity Analysis

Time Complexity: O(log n)
  • Finding node: O(log n)
  • Deleting node: O(1)
  • Rebalancing (multiple rotations): O(log n)
  • Total: O(log n)

⚡ Performance Analysis

Operation AVL Tree (Average) AVL Tree (Worst) BST (Average) BST (Worst)
Search O(log n) O(log n) O(log n) O(n)
Insertion O(log n) O(log n) O(log n) O(n)
Deletion O(log n) O(log n) O(log n) O(n)
Traversal O(n) O(n) O(n) O(n)

Space Complexity

O(n) - AVL trees store n nodes plus height information at each node

💡 Why AVL Trees are Better:
  • Predictable: No worst-case O(n) operations
  • Balanced: Always maintains logarithmic height
  • Efficient: All operations guaranteed O(log n)
  • Reliable: Performance doesn't depend on insertion order

💻 Key Implementation Concepts

Node Structure

public class AVLNode { int key; int height; AVLNode left, right; public AVLNode(int key) { this.key = key; this.height = 1; // New node is initially at height 1 } }

Essential Functions

1. Height Calculation

protected int height(Position p) { return tree.getAux(p); // Stored as auxiliary data } protected void recomputeHeight(Position p) { int h = 1 + Math.max(height(left(p)), height(right(p))); tree.setAux(p, h); }

2. Balance Factor Check

protected boolean isBalanced(Position p) { return Math.abs(height(left(p)) - height(right(p))) <= 1; }

3. Taller Child Selection

protected Position tallerChild(Position p) { if (height(left(p)) > height(right(p))) return left(p); // Left is taller if (height(left(p)) < height(right(p))) return right(p); // Right is taller // Equal height: match parent's orientation if (p == left(parent(p))) return left(p); // Return aligned child else return right(p); }

4. Rebalancing After Insertion

protected void rebalanceInsert(Position p) { rebalance(p); // Check balance and fix if needed } protected void rebalance(Position p) { int oldHeight, newHeight; do { oldHeight = height(p); if (!isBalanced(p)) { // Perform trinode restructuring p = restructure(tallerChild(tallerChild(p))); recomputeHeight(left(p)); recomputeHeight(right(p)); } recomputeHeight(p); newHeight = height(p); p = parent(p); } while (oldHeight != newHeight && p != null); }

5. Rebalancing After Deletion

protected void rebalanceDelete(Position p) { if (!isRoot(p)) rebalance(parent(p)); // Must check from parent up to root }

📖 Study Tips & Common Mistakes

✅ Key Concepts to Master

  • Understanding balance factor calculation
  • Identifying which rotation to use (same vs opposite signs)
  • Recognizing that insertion needs only ONE rotation
  • Remembering that deletion may need MULTIPLE rotations
  • Height calculation after rotations
  • Trinode restructuring process

⚠️ Common Mistakes to Avoid

  1. Forgetting to update heights after rotations
  2. Stopping at first rotation during deletion (must go to root!)
  3. Wrong rotation selection - remember same sign = single, opposite = double
  4. Not maintaining BST property during rotations
  5. Calculating balance factor incorrectly (it's left - right, not right - left)

🎯 Practice Problems

  1. Insert nodes 45, 70, 35, 3, 74, 25, 81, 4 into an empty AVL tree. Show all rotations.
  2. Delete node 25 from the tree created above. Show all rebalancing steps.
  3. Given a tree of height h, prove the minimum number of nodes is approximately Fibonacci(h+2).
  4. Compare AVL trees with Red-Black trees - when would you use each?

🔍 Quick Reference

Rotation Decision Tree: 
Is node unbalanced (|BF| = 2)?
├─ NO → Continue checking parent
└─ YES → Which subtree is taller?
    ├─ Left (BF = +2)
    │   ├─ Left child's left subtree taller → LL: Single Right Rotation
    │   └─ Left child's right subtree taller → LR: Double Rotation (Left-Right)
    └─ Right (BF = -2)
        ├─ Right child's right subtree taller → RR: Single Left Rotation
        └─ Right child's left subtree taller → RL: Double Rotation (Right-Left)

📋 Summary

AVL Tree Advantages

  • ✅ Guaranteed O(log n) for search, insert, delete
  • ✅ More strictly balanced than Red-Black trees
  • ✅ Better search performance (fewer comparisons)
  • ✅ Predictable performance regardless of input order

AVL Tree Disadvantages

  • ❌ More rotations during insertion/deletion than Red-Black trees
  • ❌ Extra space for height storage at each node
  • ❌ More complex implementation than simple BST
  • ❌ Slightly slower insertions/deletions compared to Red-Black trees

🎓 Remember for Exams

  • Height of AVL tree with n nodes: h = O(log n)
  • Balance factor range: -1, 0, +1
  • All operations: O(log n)
  • Space complexity: O(n)
  • Insertion: 1 rotation max
  • Deletion: O(log n) rotations possible
  • Rotation time: O(1)

🎓 Practice Questions

Question 1: Define AVL Tree Balance Factor

Q: What is the balance factor of a node, and what values indicate a valid AVL tree versus an unbalanced one?

A: The balance factor of a node is calculated as height(left subtree) - height(right subtree). Valid balance factors in an AVL tree are -1, 0, or +1. A value of +2 means the left subtree is two levels taller (rotate right), and -2 means the right subtree is two levels taller (rotate left). Any node with |BF| = 2 is unbalanced and triggers a rotation.

Question 2: The Four Rotation Types

Q: How do you determine which of the four rotations (LL, RR, LR, RL) to apply?

A: Check the balance factor of the unbalanced node and its taller child:
- BF = +2 and child BF = +1 (LL): Single right rotation at the unbalanced node.
- BF = -2 and child BF = -1 (RR): Single left rotation at the unbalanced node.
- BF = +2 and child BF = -1 (LR): Left rotation on the child, then right rotation on the unbalanced node.
- BF = -2 and child BF = +1 (RL): Right rotation on the child, then left rotation on the unbalanced node.
The quick rule: same sign → single rotation; opposite signs → double rotation.

Question 3: Why Is AVL Height O(log n)?

Q: Sketch the proof that an AVL tree with n nodes has height h < 2 log n + 2.

A: Define n(h) as the minimum number of nodes in an AVL tree of height h. The recurrence is n(h) = 1 + n(h-1) + n(h-2), with n(1) = 1, n(2) = 2. Since n(h-1) > n(h-2), we get n(h) > 2·n(h-2), which by induction gives n(h) > 2^(h/2 - 1). Solving for h yields h < 2 log n(h) + 2, so h = O(log n). This is the fundamental reason all AVL operations are O(log n).

Question 4: Trace an Insertion

Q: Insert the values 30, 20, 40, 10, 25 into an empty AVL tree, step by step. Which rotation (if any) is needed after each insertion?

A: 1. Insert 30 → root, balanced.
2. Insert 20 → left child of 30, balanced.
3. Insert 40 → right child of 30, balanced.
4. Insert 10 → left child of 20, balanced.
5. Insert 25 → right child of 20. Node 30 has BF = +2 (left subtree height 2, right height 1). Node 20 has BF = -1 (LR case: opposite signs). Apply Left-Right double rotation: left-rotate at 20, then right-rotate at 30. Result: 25 becomes the new root of that subtree, with 20 as its left child and 30 as its right child.

Question 5: Insertion vs. Deletion — Number of Rotations

Q: Why does insertion require at most ONE rotation, while deletion may require O(log n) rotations?

A: During insertion, a single rotation restores the height of the subtree to what it was before the insertion. Because the height is restored, no ancestor can become unbalanced — the fix propagates no further. During deletion, a rotation may reduce the height of a subtree by one, which can propagate imbalance upward to the parent, grandparent, and so on all the way to the root. Each level may need its own rotation, giving up to O(log n) rotations in the worst case.

Question 6: AVL vs. Regular BST Worst Case

Q: Give a concrete example of a sequence of insertions that causes a regular BST to degrade to O(n) search, and explain why the same sequence causes no problem for an AVL tree.

A: Inserting 1, 2, 3, 4, 5 in sorted order into a BST creates a right-skewed chain (like a linked list) with height n-1 = 4, so search is O(n). In an AVL tree, after inserting 3 the tree is balanced (1→2→3 triggers an RR left rotation, making 2 the root with 1 and 3 as children). Subsequent insertions are similarly rebalanced. The AVL tree's height stays at ⌊log n⌋, guaranteeing O(log n) search regardless of insertion order.

Question 7: Exam Trap — Updating Heights

Q: After performing a rotation, which nodes' heights must be updated and in what order? What goes wrong if you skip this step?

A: After a rotation that makes node b the new root of a subtree (with children a and c), you must update heights in the order: recomputeHeight(a), recomputeHeight(c), then recomputeHeight(b) — children before parent. If you skip height updates, balance factor checks above the rotated subtree will use stale values and incorrectly report the tree as balanced (or unbalanced) when it is not, leading to missed rotations or spurious rotations on subsequent operations.

Question 8: Space and Time Complexity Summary

Q: State the time and space complexity for search, insert, delete, and traversal in an AVL tree, and justify each.

A: - Search: O(log n) — height is O(log n), we follow at most one root-to-leaf path.
- Insert: O(log n) — BST insert O(log n) + at most one O(1) rotation + O(log n) height updates.
- Delete: O(log n) — BST delete O(log n) + O(log n) rotations (one per level) each O(1).
- Traversal: O(n) — every node visited once.
- Space: O(n) — n node objects, each storing an extra integer for height.