One invariant, enforced at every node, that makes search, minimum, successor, and sorted traversal all fall out of the same shape — for O(h) each, where h is a height you do not yet control.
A hash table is faster than a binary search tree at the only thing a hash table can do. The BST earns its place by doing everything else: it supports MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR, and in-order traversal, none of which hashing can offer at any cost. Every operation runs in O(h) on a tree of height h. That bound is the chapter’s whole story: on a balanced tree h = Θ(lg n) and everything is fast, but on a tree built by inserting sorted data h = n - 1 and the structure degenerates into a linked list. Chapter 12 establishes the operations and measures the damage; Chapter 13 fixes it.
TRANSPLANT helper, which is the cleanest presentation of the three cases and worth learning in that form.A BST is a binary tree where each node holds key, satellite data, and three pointers: left, right, and p (parent). A missing child or the root’s parent is NIL. The structure is organised by one rule.
x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key ≤ x.key. If y is a node in the right subtree of x, then y.key ≥ x.key.O(1) and nothing else, while a BST gives you the entire sorted order.The property has an immediate and beautiful consequence.
INORDER-TREE-WALK(x)
1 if x ≠ NIL
2 INORDER-TREE-WALK(x.left)
3 print x.key
4 INORDER-TREE-WALK(x.right)Left subtree, then the node, then the right subtree. Prints all keys in sorted order, in Θ(n) time.
Why Θ(n): the walk visits each of the n nodes exactly once and does Θ(1) work per visit. The book proves it more carefully with a recurrence T(n) = T(k) + T(n-k-1) + d, which solves to (c+d)n + c by substitution — a nice exercise in the Chapter 4 technique.
The property tells you which way to go at every node, so search never needs to backtrack.
TREE-SEARCH(x, k)
1 if x == NIL or k == x.key
2 return x
3 if k < x.key
4 return TREE-SEARCH(x.left, k)
5 else
6 return TREE-SEARCH(x.right, k)
ITERATIVE-TREE-SEARCH(x, k) // same thing, no stack frames
1 while x ≠ NIL and k ≠ x.key
2 if k < x.key
3 x = x.left
4 else x = x.right
5 return xBoth run in O(h). The iterative version is what you should write — the recursion is tail recursion, and unrolling it avoids h stack frames.
The path traced is a single root-to-node path, which is why the cost is the height and not the node count. Binary search over an array does the same thing; the tree just makes the structure explicit and mutable.
TREE-MINIMUM(x) TREE-MAXIMUM(x)
1 while x.left ≠ NIL 1 while x.right ≠ NIL
2 x = x.left 2 x = x.right
3 return x 3 return xWalk left as far as possible, or right as far as possible. O(h).
Correctness is the BST property applied once: if x has no left child, nothing in the tree rooted at x is smaller than x, because everything smaller would have had to be in that missing left subtree.
The successor of x is the node with the smallest key greater than x.key — the next node an in-order walk would print. This is the operation that hash tables cannot do at all, and it splits into two cases.
TREE-SUCCESSOR(x)
1 if x.right ≠ NIL
2 return TREE-MINIMUM(x.right) // case 1: go down
3 else // case 2: go up
4 y = x.p
5 while y ≠ NIL and x == y.right
6 x = y
7 y = y.p
8 return yx was the maximum and the successor is NIL.TREE-PREDECESSOR is the exact mirror: if there is a left subtree, take its maximum; otherwise climb until you arrive from a right child. Both are O(h).
Insertion walks down as if searching, remembering the parent, and hangs the new node where the search fell off the tree.
TREE-INSERT(T, z)
1 x = T.root // node being compared with z
2 y = NIL // y will be the parent of z
3 while x ≠ NIL // descend until reaching a leaf position
4 y = x
5 if z.key < x.key
6 x = x.left
7 else x = x.right
8 z.p = y // found the parent
9 if y == NIL
10 T.root = z // the tree was empty
11 elseif z.key < y.key
12 y.left = z
13 else y.right = zO(h). The trailing pointer y exists because once x becomes NIL you have lost the parent, and the new node needs one.
A new node is always inserted as a leaf. No existing node moves, and no pointers other than the new parent’s change. That simplicity is exactly what makes the tree vulnerable to bad insertion orders — nothing ever rebalances.
Deletion is the only genuinely fiddly operation. CLRS factors out the common bookkeeping first.
TRANSPLANT(T, u, v) // replace subtree u with subtree v
1 if u.p == NIL
2 T.root = v
3 elseif u == u.p.left
4 u.p.left = v
5 else u.p.right = v
6 if v ≠ NIL
7 v.p = u.pSplices the subtree rooted at v into the position held by u. Handles the root case and both child cases.
TRANSPLANT does not do. It never touches v.left or v.right. The caller is responsible for those. Forgetting this is the most common bug when implementing deletion from the book.Removing node z splits by how many children it has.
| Case | Situation | Action |
|---|---|---|
| 1 | z has no left child | Replace z with its right child (possibly NIL). |
| 2 | z has a left child but no right child | Replace z with its left child. |
| 3 | z has two children | Find y, the successor of z (the minimum of z’s right subtree). Splice y out of its position, then put y where z was. |
TREE-DELETE(T, z)
1 if z.left == NIL
2 TRANSPLANT(T, z, z.right) // case 1
3 elseif z.right == NIL
4 TRANSPLANT(T, z, z.left) // case 2
5 else
6 y = TREE-MINIMUM(z.right) // case 3: y is z's successor
7 if y ≠ z.right // y is deeper in the right subtree
8 TRANSPLANT(T, y, y.right) // lift y out first
9 y.right = z.right
10 y.right.p = y
11 TRANSPLANT(T, z, y) // put y in z's place
12 y.left = z.left
13 y.left.p = yO(h), dominated by the TREE-MINIMUM call in case 3.
Collecting the results:
| Operation | Cost | Balanced h = Θ(lg n) | Degenerate h = n-1 |
|---|---|---|---|
SEARCH | O(h) | O(lg n) | O(n) |
MINIMUM, MAXIMUM | O(h) | O(lg n) | O(n) |
SUCCESSOR, PREDECESSOR | O(h) | O(lg n) | O(n) |
INSERT | O(h) | O(lg n) | O(n) |
DELETE | O(h) | O(lg n) | O(n) |
| In-order walk | Θ(n) | Θ(n) | Θ(n) |
n-1, and the BST is a linked list with extra pointers. Sorted input is extremely common: timestamps, auto-increment IDs, alphabetised names, data loaded from an already-sorted file. A plain BST fed real-world data very often ends up in exactly this state.Section 12.4 asks how bad this is on average, and the answer is reassuring in theory.
n distinct keys is one produced by inserting the keys in a uniformly random order.n distinct keys is O(lg n).The proof is a genuinely clever one and worth knowing the shape of. Bounding the expected height directly is hard because the maximum of random variables does not commute with expectation. CLRS instead studies the exponential height Yₙ = 2Xₙ, where Xₙ is the height. Because the exponential turns the maximum of the two subtree heights into something tractable, the recurrence can be solved, giving E[Yₙ] = O(n³). Then Jensen’s inequality, which says 2E[Xₙ] ≤ E[2Xₙ], converts that back into E[Xₙ] = O(lg n).
≤ the node, everything in the right subtree is ≥ it. It constrains whole subtrees, unlike the heap property, which constrains only children.Θ(n). That is the BST property restated.O(h), because each traces one root-to-node path.TRANSPLANT replaces one subtree with another and fixes only the parent links. The caller must fix the children.h. Balanced gives Θ(lg n); sorted insertion order gives h = n-1 and a linked list.O(lg n), proved via exponential height and Jensen’s inequality. Cold comfort when your input is sorted.Chapter 13 removes the dependence on luck. A red-black tree is a BST carrying one extra bit per node, plus four colour invariants that together force the height to be O(lg n) on every input, guaranteed. Search, minimum, successor, and the in-order walk are inherited unchanged from this chapter; only insertion and deletion gain the rebalancing machinery needed to maintain the invariants.