Data Structures and Algorithms: the questions likely to come

AVL Tree

An AVL tree is a self-balancing binary search tree in which, for every node, the heights of its left and right subtrees differ by at most 1. The balance factor $BF = h_{left} - h_{right}$ must be in $\{-1, 0, +1\}$. After every insertion/deletion that violates this, balance is restored by one of four rotations: LL (single right), RR (single left), LR (left-right), RL (right-left). This guarantees height $O(\log n)$, so search/insert/delete are $O(\log n)$.

Construct AVL Tree for: 23, 30, 39, 11, 7, 17, 28, 18

Insert 23, 30:

  23
    \
     30

Insert 39 — 23 becomes unbalanced (BF = -2), right-right case → RR rotation (left) about 23:

     30
    /  \
   23   39

Insert 11, 7 — inserting 7 makes 23 unbalanced (BF = +2), left-left case → LL rotation (right) about 23:

        30
       /  \
      11   39
     /  \
    7    23

Insert 17 — goes left of 23. Check ancestors: node 11 has BF = +1, node 30 has BF = +2 (left heavy) and the insertion is in the left subtree's right side → LR case. First left-rotate 11, then right-rotate 30:

        23
       /  \
      11   30
     / \     \
    7  17     39

Insert 28 — goes left of 30 (right child of 23). Tree stays balanced (all BFs in range):

        23
       /  \
      11   30
     / \   / \
    7  17 28  39

Insert 18 — goes right of 17. Now check ancestors of 18: node 17 BF = -1, node 11 BF = -2 (right heavy) and insertion is in the right subtree's left side → RL case about 11. First right-rotate 17... since 17's right child 18 is the imbalance, RL = right-rotate(17's child) then left-rotate(11). Result lifts 17 up:

          23
         /  \
       17    30
      /  \   / \
     11  18 28  39
    /
   7

Final AVL Tree

          23
         /  \
       17    30
      /  \   / \
     11  18 28  39
    /
   7

Verification of balance factors:

• 7: leaf, BF = 0
• 11: left height 1, right 0 → BF = +1 ✓
• 18: leaf, BF = 0
• 17: left height 2, right 1 → BF = +1 ✓
• 28, 39: leaves, BF = 0
• 30: BF = 0
• 23 (root): left height 3, right height 2 → BF = +1 ✓

All balance factors lie in $\{-1, 0, +1\}$, so the tree is a valid AVL tree.