COMP9123 — Data Structures & Algorithms
Week 5: Binary Search Trees & AVL Trees
Week 5 adds order to binary trees and turns them into search structures. The lecture first teaches the BST invariant and the path-based logic behind search, insert, delete, and range queries. Then it makes the deeper point: order alone is not enough, because performance is really controlled by height, which is why AVL balancing matters.
The central Week 5 lesson is that correctness and speed come from different invariants: BST order gives correct search, while AVL balance keeps that search logarithmic.
BST Property: Why Inorder Suddenly Becomes Powerful
A binary search tree is not just a binary tree that happens to hold keys. It is a binary tree whose structure must obey a global order rule: every key in the left subtree is smaller than the node, and every key in the right subtree is larger.
| Idea | What it means | Why it matters |
|---|---|---|
| Left subtree | All keys are strictly smaller than the current node's key. | One comparison is enough to rule out the whole right side. |
| Right subtree | All keys are strictly larger than the current node's key. | One comparison is enough to rule out the whole left side. |
| Recursive property | Both subtrees must themselves be BSTs. | The invariant holds at every scale, not just near the root. |
| Inorder traversal | Visit left subtree, node, right subtree. | This yields keys in increasing order, which is the signature proof fact for BSTs. |
Internal vs external nodes
The slides simplify the implementation by storing keys only at internal nodes. External positions act like search endpoints where insertion can happen.
Global, not local
The BST property is stronger than “left child smaller, right child larger.” Every node in the full left subtree must be smaller, and every node in the full right subtree must be larger.
Search Paths: Almost Everything Is a Guided Walk Downward
Once the keys are arranged by order, the core BST operations stop looking like scans. Search is just repeated comparison followed by a left or right decision, so the algorithm follows a single root-to-leaf path instead of touching every node.
If the target is smaller
Go left. The entire right subtree is guaranteed to be too large to contain the key.
If the target is larger
Go right. The entire left subtree is guaranteed to be too small to contain the key.
If the target matches
Stop. The order invariant means you have found the unique correct position for that key.
The real runtime story of BST search
def search(k, v):
if v is external:
return v
if k == key(v):
return v
if k < key(v):
return search(k, v.left)
return search(k, v.right)
Search time is \(O(h)\), where \(h\) is the height of the tree. That is the key phrase for Week 5. The operation is efficient only if the tree stays shallow.
Professor lens: do not say BST search is \(O(\log n)\) by default. The correct statement is \(O(h)\), which becomes \(O(\log n)\) only when the tree is balanced well enough.
Insert & Delete: Preserving Order While the Shape Changes
Insertion is conceptually simple because it is just search followed by expansion at the correct external position. Deletion is where the BST invariant starts to feel more delicate, because removing a node can disturb the shape in several different ways.
| Operation case | What happens | Why order is preserved |
|---|---|---|
| Insert key \(k\) | Search until the correct external position is reached, then create the new internal node there. | The search path guarantees that every ancestor still sees the new key on the correct side. |
| Delete with zero or one internal child | Remove the node and promote its remaining child. | The promoted subtree already fits the same key interval. |
| Delete with two internal children | Replace the node with its inorder successor from the right subtree, then delete that successor. | The successor is the next larger key, so sorted order is preserved. |
The inorder successor is the smallest key in the deleted node's right subtree.
So it is larger than every key in the left subtree, but no larger than any other key that remains on the right.
Replacing the deleted key with that successor keeps the inorder sequence sorted.
Week 5 repeatedly returns to one sentence: search, insert, and delete all take \(O(h)\), so the real performance question is not which of those operations you choose but what the height becomes.
Range Queries: Using Order to Skip Whole Subtrees
Range search is where BST structure starts paying off beyond single-key lookup. Instead of checking every key against an interval \([k_1, k_2]\), the algorithm uses the BST invariant to prune large parts of the tree instantly.
The pruning idea in one block of pseudocode
def range(v, k1, k2):
if v is external:
return
if key(v) > k2:
range(v.left, k1, k2)
elif key(v) < k1:
range(v.right, k1, k2)
else:
range(v.left, k1, k2)
output.add(v)
range(v.right, k1, k2)
| If the current key is... | What you can conclude | What subtree can be skipped |
|---|---|---|
| Greater than \(k_2\) | Everything in the right subtree is also too large. | Skip the whole right subtree. |
| Smaller than \(k_1\) | Everything in the left subtree is also too small. | Skip the whole left subtree. |
| Inside \([k_1, k_2]\) | The current key belongs in the answer. | Neither side is immediately skippable, so recurse both ways. |
Why this is better than scanning: the BST invariant turns “not in range” into a structural argument about entire subtrees, not just the current node.
AVL Motivation: BST Correctness Is Not Yet a Performance Guarantee
A plain BST can still collapse into a chain, which means height can become \(n-1\) and all the elegant \(O(h)\) operations quietly become linear. AVL trees are the course's answer to that problem: keep the search-tree invariant, but add a balance condition strong enough to force logarithmic height.
What AVL stores
Each node tracks the height of its subtree, so local balance can be checked without recomputing height from scratch.
Balance condition
The heights of the two child subtrees of every internal node differ by at most 1.
Payoff
If the tree stores \(n\) keys, its height stays \(O(\log n)\), so search, insertion, and deletion stay logarithmic as well.
Slide 78's key implementation lesson: height must be maintained incrementally. If you recompute subtree heights from scratch after every update, the balancing overhead would destroy the efficiency you were trying to protect.
The conceptual split: BST order tells you where a key belongs. AVL balance tells you the root-to-key path will stay short enough for that search to be fast.
Rotations & Rebalancing: Repair the Shape Without Breaking the Order
AVL repair starts after an ordinary BST insertion or deletion. You walk upward, find the first ancestor whose child heights differ by 2, then use the \(x,y,z\) trinode pattern to restructure that local region.
Find \(z\)
\(z\) is the lowest ancestor that has become unbalanced.
Find \(y\)
\(y\) is the taller child of \(z\).
Find \(x\)
\(x\) is the child of \(y\) that lies on the heavy path.
| Heavy pattern | Shape intuition | Repair |
|---|---|---|
| LL | Outer-heavy on the left | Single right rotation |
| RR | Outer-heavy on the right | Single left rotation |
| LR | Inner-heavy: left then right | Double rotation |
| RL | Inner-heavy: right then left | Double rotation |
The affected region can be described as three ordered nodes \(a,b,c\) with four ordered subtrees \(T_0,T_1,T_2,T_3\).
Restructuring changes only which of \(a,b,c\) sits on top; it does not change the inorder left-to-right order of the subtrees.
So the tree becomes shorter locally while the search-tree ordering stays intact.
Tutorial & Code: The Course Starts Asking Design Questions
Tutorial 5 does more than rehearse BST operations. It asks you to prove inorder sortedness, spot flawed BST validation logic, find largest and second-largest keys in \(O(h)\), support median with subtree-size augmentation, and reason about range deletion in \(O(h+s)\).
| Tutorial / code item | Main idea it is testing | Why it matters |
|---|---|---|
| Problem 2 | Inorder traversal of a BST is sorted | This is the proof fact behind many BST arguments. |
| Problem 6 | Local child comparisons are not enough to validate a BST | You must reason with key ranges, not just immediate edges. |
| Problems 7 and 8 | Largest / second-largest in \(O(h)\) | Good practice in structural case analysis. |
| Problems 9 and 10 | Augmentation and range deletion | The course starts turning trees into query data structures, not just storage shapes. |
What the AVL code skeleton is really about
class AVL(Generic[T]):
def restructure(self, p):
# restore local balance
def search(self, k, p):
# follow one path based on comparisons
def insert(self, k):
# BST insert first, then rebalance
def remove(self, k):
# BST remove first, then rebalance
def range_search(self, lower, upper):
# prune by interval using BST order
The skeleton is reinforcing the lecture's main architecture: order controls navigation, metadata controls balance, and rotations are the local repair mechanism.
Best Week 5 checkpoint: you should be able to explain why a correct BST can still be slow, and why an AVL tree fixes that without changing the fundamental search-tree ordering.
Quiz Hub & Revision Targets
Use mixed practice only after you can already explain the two central invariants in plain language: BST order and AVL balance. If those are fuzzy, the algorithm details will keep feeling arbitrary.
You should be able to explain
Why inorder of a BST is sorted, and why search, insert, and delete are path-based rather than full scans.
You should be able to distinguish
BST correctness from AVL performance guarantees, and single from double rotation cases.
You should be able to design
A range-search or augmented-BST method that uses the invariant to skip work instead of brute-forcing the whole tree.
Suggested sequence: finish the foundations page next for the proof toolkit, then come back for mixed practice once the logic behind rotations, inorder, and subtree-size augmentation feels stable.