COMP90038 · Algorithms And Complexity
Balanced Search Trees: AVL and 2-3
A binary search tree gives O(log n) search only if it stays short — and a plain BST can degenerate to a linked list (height n) on sorted input, the trap this chapter exists to fix. Self-balancing trees keep the height Θ(log n) guaranteed. AVL trees track a balance factor (height of left subtree minus right) at every node and, whenever an insert pushes it outside {−1, 0, +1}, restore balance with one of four rotations — single LL and RR, double LR and RL — chosen by the shape of the imbalance. 2-3 trees take a different route: nodes hold one or two keys (2-nodes and 3-nodes), all leaves sit at the same depth, and growth happens by splitting an over-full node and promoting its middle key upward, so the tree stays perfectly height-balanced. Both deliver O(log n) search, insert and delete. The exam hand-traces an AVL insert sequence (Q1 routinely asks you to insert 8 keys and rebalance) and a 2-3 build with a count of 3-nodes, so the rotation rules and the split-and-promote rule must be exact.
What this chapter covers
- 01BST recap and the height = O(log n)? degeneration trap
- 02AVL balance factor and when an insert breaks it
- 03The four rotations: single LL / RR, double LR / RL
- 042-3 trees: 2-nodes and 3-nodes, all leaves at the same depth
- 05Split-and-promote insertion; guaranteed O(log n) operations
Worked example: an AVL rotation
- +1Insert 10, then 20. Tree is 10 with right child 20; balance factor of 10 is −1 — still allowed.
- +1Insert 30. Now 10→20→30 is a right-leaning chain; balance factor of 10 is −2 — unbalanced.
- +1Diagnose and rotate. The imbalance is right-right (RR), so a single left rotation about 10 lifts 20 to the root.
- +1Result. Root 20 with children 10 and 30 — height 1, balanced, all factors 0.
Key terms
- Self-balancing BST
- A binary search tree that performs rebalancing operations on insert/delete to keep its height Θ(log n), so search, insert and delete stay O(log n) even on adversarial input. AVL and 2-3 trees are the two studied here.
- Balance factor
- For an AVL node, the height of its left subtree minus the height of its right subtree. The AVL invariant keeps every balance factor in {−1, 0, +1}; an insert that pushes one to ±2 triggers a rotation.
- AVL rotation
- A local O(1) restructuring that restores the AVL balance invariant after an insert or delete. Four cases: single LL and RR for straight-line imbalances, double LR and RL for zig-zag imbalances, chosen by the shape of the unbalanced path.
- 2-3 tree
- A balanced search tree whose nodes hold one key (2-node, two children) or two keys (3-node, three children), with all leaves at the same depth. Insertion splits over-full nodes and promotes the middle key, keeping the tree height-balanced.
- Split and promote
- The 2-3 insertion mechanism: when a node would hold three keys, split it into two 2-nodes and push the middle key up to the parent, which may cascade to the root and increase the tree's height by one.
Balanced Search Trees: AVL and 2-3 FAQ
Why isn't a plain BST good enough?
Because a plain BST's height depends on insertion order. Insert sorted keys and it degenerates into a linked list of height n, making search O(n). Self-balancing trees guarantee height Θ(log n) no matter the order, which is the whole point of AVL and 2-3 trees.
How do I choose which AVL rotation to apply?
Find the lowest unbalanced node and look at the two steps down toward the newly inserted key. Same direction twice (left-left or right-right) → a single rotation; a zig-zag (left-right or right-left) → a double rotation. The shape of the path, not the keys, picks the rotation.
How does a 2-3 tree grow taller?
Only by splitting the root. Inserts push the middle key of an over-full node up to its parent; if that cascades all the way to the root and the root itself splits, the promoted middle key becomes a new root and every leaf's depth increases by one at once — which is why all leaves stay level.
Exam move
Practise AVL inserts as full hand-traces, because Q1 famously asks you to insert eight keys one by one and rebalance — a single mark but a multi-minute trace where one wrong rotation cascades. Drill diagnosing the four rotation cases from the shape of the unbalanced path, and the 2-3 split-and-promote rule with a count of 3-nodes. Be able to state in a Q2 justification why both structures guarantee O(log n) (bounded height) and why a plain BST does not (order-dependent degeneration). Speed here is bankable open-book marks.
