AVL Tree

Definition

• An AVL Tree (Adelson-Velsky and Landis, 1962) is a self-balancing Binary Search Tree where, for every node, the height difference between left and right subtrees (the Balance Factor) is at most 1
• Balance Factor: $\text{BF}(x) = \text{height}(\text{left subtree}) - \text{height}(\text{right subtree})$; must be in $\{-1, 0, +1\}$ for every node

Why It Exists

• A plain BST can degrade to O(n) (skewed/linked-list shape) with unlucky insertion order — AVL guarantees O(log n) height always, so search/insert/delete stay O(log n) worst case

Rebalancing via Rotations

When an insertion/deletion violates the balance factor, one of four rotations restores balance:

1. LL Rotation (Left-Left case) — single right rotation
2. RR Rotation (Right-Right case) — single left rotation
3. LR Rotation (Left-Right case) — left rotation then right rotation (double)
4. RL Rotation (Right-Left case) — right rotation then left rotation (double)

Complexity

• Search, Insert, Delete: O(log n) worst case, guaranteed (the key advantage over plain BST)
• Extra overhead: rebalancing cost on every insert/delete (constant factor overhead vs plain BST)

AVL vs Plain BST vs Red-Black Tree (comparison context)

Exam Angle

Expect to be asked to trace an insertion causing an imbalance and identify which rotation (LL/RR/LR/RL) fixes it — practice drawing these by hand. Know AVL trades faster search for slightly slower insert/delete (due to rotation overhead) compared to Red-Black Trees.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Full Construction Trace (the exact skill examiners test)

2016, Paper I, Q6(c) (6 marks) — In AVL tree balance factor of every node is -1 or 0 or +1. We can calculate the balance factor as $\text{Height(left-sub-tree)} - \text{Height(right-sub-tree)}$. Construct AVL tree from the given data: A = {8, 14, 2, 26, 10, 12, 16, 28, 20, 7}

Insert one key at a time (standard BST insertion), rebalancing whenever a node's balance factor leaves {-1, 0, +1}:

• Insert 8, 14, 2, 26, 10 → tree stays within balance, no rotation needed.
• Insert 12 → BF(8) = −2, and its right child 14 is itself left-heavy (BF = +1) → RL case: rotate right at 14, then rotate left at 8.
• Insert 16, 28 → no rotation needed.
• Insert 20 → BF(14) = −2, and its right child 26 is left-heavy (BF = +1) → RL case again: rotate right at 26, then rotate left at 14.
• Insert 7 → BF(8) = +2, and its left child 2 is right-heavy (BF = −1) → LR case: rotate left at 2, then rotate right at 8.

Final AVL tree (all 10 keys present):

     10
   /    \
  7      16
 / \    /   \
2   8  14    26
       /     /  \
      12    20   28

Balance factors: 10:−1, 7:0, 2:0, 8:0, 16:0, 14:+1, 12:0, 26:0, 20:0, 28:0 — every node is within {-1,0,+1}, confirming a valid AVL tree.

Key reasoning points:

• A tree built from 10 inserted keys must contain all 10 nodes — don't drop a node from the final diagram just because it doesn't trigger a rotation (12 never causes an imbalance itself, but it must still appear as 14's left child).
• Both violations above are RL cases: always check the child's balance factor (not just which side made the parent unbalanced) to name the rotation case correctly — a right-heavy parent with a left-heavy right child is RL, not RR.

📝 Why AVL Over the Alternatives

2026, Paper I, Q8(c) (8 marks) — A company maintains millions of product IDs and frequently performs searching, insertion, and deletion. The data volume is extremely large, and performance is critical. Which data structure would be most suitable — Binary Search Tree, AVL Tree, Hash Table, or Array? Justify your answer logically using time complexity and memory considerations.

• Unsorted array: O(n) search, O(n) deletion — too slow at scale.
• Sorted array: O(log n) search but O(n) insert/delete (shifting) — unacceptable at scale.
• Plain BST: average O(log n), but sequential/near-sorted product-ID batches can degrade it to O(n) (linked-list shape).
• AVL Tree: guarantees O(log n) worst-case search/insert/delete via rotations — solid, but still logarithmic, not constant.
• Hash Table: average-case O(1) search/insert/delete with a good hash function and load-factor management — the fastest option when no sorted/range access is required.

Answer: Hash Table — since the question emphasizes raw speed at scale with no stated need for sorted/range access, O(1) average case beats O(log n). AVL is the recommended fallback only if worst-case guarantees or sorted/range queries are also required.

📝 Self-Balancing BSTs — When They're Preferred

2025, Paper I, Q6(a) (6 marks) — What are self-balancing Binary Search Trees? Under what circumstances are they preferred over a plain Binary Search Tree?

A self-balancing BST (AVL, Red-Black) automatically re-arranges via rotations after insert/delete to keep height at O(log n), instead of allowing it to degrade into a skewed shape. AVL enforces balance factor ∈ {-1,0,+1} at every node; Red-Black uses colour properties to bound height at $\leq 2\log_2(n+1)$.

Preferred when: insertions/deletions are frequent and unpredictable and worst-case guarantees matter (databases, real-time systems, language runtime maps/sets); input order can't be controlled and might be sorted/adversarial; consistently fast O(log n) is needed regardless of insertion sequence. A plain BST is acceptable only for random-order or rarely-modified data, since balancing adds rotation overhead.

📝 Core Definition

2019, Paper I, Q6(b) (5 marks) — What is AVL tree? Under what condition does a binary tree become an AVL tree?

An AVL tree (Adelson-Velsky & Landis) is a self-balancing BST in which the heights of the two child subtrees of any node differ by at most one — this is the balance factor, which must be −1, 0, or +1 for every node. A BST becomes an AVL tree precisely when this condition holds at every single node. Whenever insert/delete pushes a node's BF outside {-1,0,1}, one of four rotations (LL, RR, LR, RL) restores it — guaranteeing O(log n) height and hence O(log n) worst-case operations, unlike an unbalanced BST which can degrade to O(n).

📝 What Happens Without Balancing

2018, Paper I, Q5(c) (7 marks) — Random insertion of nodes into a binary search tree would result in what type of tree shape? Elaborate.

If keys are inserted in a genuinely random order, the expected height of the resulting BST is O(log n) (≈ 2 ln n) — comparable to how randomized quicksort behaves well on average without explicit balancing. But this is only an average-case guarantee: for an unlucky order — most notably already-sorted ascending/descending insertion — the tree degenerates into a fully skewed, linked-list shape with height O(n), giving O(n) worst-case search/insert/delete.

Exam angle: This is precisely the motivation for AVL/Red-Black trees — applications needing a guaranteed worst case regardless of insertion order cannot rely on hoping for a favourable random order.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q6(c) · 6 marks

Q. Construct an AVL tree from the data A = {8, 14, 2, 26, 10, 12, 16, 28, 20, 7}. (Balance factor = height of left subtree − height of right subtree, and must be −1, 0 or +1.)

Ans. Insert one key at a time and rebalance when a balance factor becomes ±2.

• Insert 8, 14, 2, 26, 10: no imbalance.
• Insert 12: the node 8 becomes right-heavy, and the heavy child 14 is left-heavy (Right-Left case). A double rotation makes 10 the subtree root with children 8 (left child 2) and 14 (children 12, 26).
• Insert 16 and 28: no imbalance.
• Insert 20: node 14 becomes right-heavy and 26 is left-heavy (Right-Left case). A double rotation makes 16 the subtree root with children 14 (left child 12) and 26 (children 20, 28).
• Insert 7: node 8 becomes left-heavy and 2 is right-heavy (Left-Right case). A double rotation makes 7 the subtree root with children 2 and 8.
• Final AVL tree:

     10
   /    \
  7      16
 / \    /  \
2   8  14   26
       /   /  \
      12  20  28

2018 · Paper-I · Q6(a) · 4 marks

Q. Define a balanced tree for both AVL and binary search tree.

Ans.

• AVL tree: a binary search tree in which, for every node, the heights of the left and right subtrees differ by at most 1. Balance factors are −1, 0 or +1.
• Binary search tree: in general a BST is balanced when its height is kept close to log₂ n, so search is O(log n). An ordinary BST has no such guarantee, and sorted input makes it skewed.

2019 · Paper-I · Q6(b) · 5 marks

Q. What is an AVL tree? Under what condition does a binary tree become an AVL tree?

Ans.

• An AVL tree (Adelson-Velsky and Landis) is a self-balancing binary search tree.
• Condition: it must be a BST, and every node must have a balance factor (height of left − height of right) of −1, 0 or +1.
• Rebalancing: when an insertion or deletion breaks the rule, rotations restore it: LL (single right), RR (single left), LR and RL (double rotations).
• Result: height is O(log n), so search, insert and delete are all O(log n).

2021 · Paper-I · Q7(a)(iii) · part of 8 marks

Q. Write a note on AVL trees.

Ans. See the definition above, plus: an AVL tree stores the height (or balance factor) in each node. It is strictly balanced, so lookups are faster than in a red-black tree, but insertions and deletions need more rotations.

2025 · Paper-I · Q6(a) · 6 marks

Q. What are self-balancing binary search trees? Under what circumstances are they preferred over a binary search tree?

Ans.

• Self-balancing BSTs (AVL, red-black, splay) automatically restructure themselves with rotations after insertion and deletion to keep the height O(log n).
• Why: an ordinary BST can degrade into a linked list (O(n)) when keys arrive in sorted order.
• Preferred when:
  • data may arrive sorted or nearly sorted
  • there are many searches and a guaranteed worst case is needed (AVL)
  • there are frequent insertions and deletions and a balance of speed is needed (red-black, used in std::map and Java TreeMap)
  • real-time or database indexing needs predictable performance
• Cost: extra memory for balance information and extra rotation work on updates.