<aside> ⚖️

L6 — Keep Trees Balanced covers BST deletion (three cases), why balancing matters, rotations (single and double), AVL trees (definition, minimum-node recurrence, logarithmic-depth proof), balance-factor implementation with a full worked insertion example, AVL deletion notes, and Java's TreeSet/TreeMap.

</aside>

📋 At a Glance

• [ ] Understand BST deletion — leaf, one-child, two-children (replace with successor)
• [ ] Know why tree balance matters — full vs sparse, best/worst/average depth
• [ ] Master four rotation types — left, right, left-right double, right-left double
• [ ] Code rotateLeft with parent-pointer updates
• [ ] Define AVL tree recursively and state the balance-factor invariant
• [ ] Derive minimum-node recurrence m(h) = m(h-1) + m(h-2) + 1
• [ ] Prove AVL height is O(log n) via induction on (3/2)^(h-1)
• [ ] Trace the full AVL insertion example (16, 51, 1, 35, 23, 45, 29, 55, 88, 91, 42, 61, 96, 58, 9, 37)
• [ ] Understand AVL deletion — may need Θ(log n) rotations
• [ ] Know TreeSet (red-black tree), TreeMap (Entry<K,V>)
• [ ] Solve Tutorial 3 Q5 (AVL insertions)

1. BST Deletion

Removing a node from a BST has three cases, ordered by difficulty.

Case 1 — Leaf Node (no children)

Simply set the parent's pointer (left or right) to null.

Example: removing 50 from the tree — just unlink it.