Store one extra field per node in a red-black tree and get a whole new operation, for free — provided the field can be recomputed from a node’s children.
You rarely invent a data structure from scratch. Far more often you take a textbook structure and hang extra information on it to support an operation it did not originally have. Chapter 17 makes that into a method: a four-step procedure, plus a theorem that tells you when the augmentation is asymptotically free. Two worked examples — order-statistic trees and interval trees — both start from the red-black tree of Chapter 13 and both keep all operations at O(lg n).
Chapter 9 found the ith smallest element of an unsorted array in O(n). Suppose instead you maintain a dynamic set and want the ith smallest at any moment, plus the reverse question: given an element, what is its rank?
x.size, the number of internal nodes in the subtree rooted at x, including x itself. Define T.nil.size = 0, which gives the identityx.size = x.left.size + x.right.size + 1size field is the only addition; keys and colours are exactly as in Chapter 13.OS-SELECT(x, i) // the ith smallest in the subtree at x
1 r = x.left.size + 1 // rank of x within its own subtree
2 if i == r
3 return x
4 elseif i < r
5 return OS-SELECT(x.left, i)
6 else
7 return OS-SELECT(x.right, i - r) // discount what is on the leftO(lg n). The shape is binary search, but on rank rather than on key. Line 7 subtracts r because the right subtree’s local ranks start over at 1.
OS-RANK(T, x) // position of x in the sorted order
1 r = x.left.size + 1
2 y = x
3 while y ≠ T.root
4 if y == y.p.right // y is a right child
5 r = r + y.p.left.size + 1 // count the parent and its left subtree
6 y = y.p
7 return rO(lg n). Walk up to the root, and every time you come up from a right child, add that parent plus everything in its left subtree, since all of those precede x.
The augmentation is only useful if size can be kept correct without slowing insertion and deletion down.
x.size at every node visited — the new node lands somewhere in each of their subtrees. O(lg n), no extra pass.After LEFT-ROTATE(T, x), where y was x.right:
y.size = x.size // y took x's whole subtree
x.size = x.left.size + x.right.size + 1 // recompute from childrenTwo assignments per rotation, and insertion does at most 2 rotations and deletion at most 3. So the augmentation adds O(1) to each and everything stays O(lg n).
size is computable from a node’s own children, so a local change requires only a local repair. Any field with that property is cheap to maintain; any field that depends on distant parts of the tree is not.1. Choose an underlying data structure.
2. Determine additional information to maintain in it.
3. Verify that the additional information can be maintained by the
basic modifying operations.
4. Develop new operations that use the information.CLRS stresses these are a guide, not a rigid order — in practice you iterate, and step 4 often reveals that step 2 chose the wrong field. Step 3 is where designs die.
f be an attribute that augments a red-black tree of n nodes, and suppose that for any node x, the value of f(x) can be computed using only the information in x, x.left, and x.right — including x.left.f and x.right.f. Then we can maintain the values of f in all nodes during insertion and deletion without asymptotically affecting the O(lg n) performance of those operations.The reason is a two-part argument you should be able to reconstruct. A change to x.f propagates only to x’s ancestors, and there are O(lg n) of them on a red-black tree. And a rotation touches only two nodes, whose f values are recomputed locally in O(1); since there are O(1) rotations per update, the total extra work is O(lg n).
| Candidate field | Computable from children? | Cheap to maintain? |
|---|---|---|
| Subtree size | Yes — sum of children plus 1 | Yes |
| Subtree min / max key | Yes | Yes |
| Subtree sum of values | Yes | Yes |
| Black-height | Yes — from a child’s black-height and colour | Yes |
| Depth of a node | No — depends on ancestors, not descendants | No. One rotation near the root changes the depth of Θ(n) nodes. |
The second example, and a more interesting one because the augmented field is used in a non-obvious way.
Each node now represents a closed interval i = [i.low, i.high]. The tree is keyed on i.low. The augmentation is x.max: the maximum high endpoint of any interval in the subtree rooted at x.
x.max = max( x.int.high, x.left.max, x.right.max )Computable from children, so Theorem 17.1 applies and max is free to maintain.
The new operation: INTERVAL-SEARCH(T, i) returns any interval in the tree that overlaps i, or T.nil.
INTERVAL-SEARCH(T, i)
1 x = T.root
2 while x ≠ T.nil and i does not overlap x.int
3 if x.left ≠ T.nil and x.left.max ≥ i.low
4 x = x.left
5 else x = x.right
6 return xO(lg n) — a single root-to-leaf descent with no backtracking.
x.left.max < i.low), then every interval in the left subtree ends before i begins, so no overlap can exist there. If it goes left, then some interval in the left subtree has high ≥ i.low; CLRS proves that if no overlap exists in the left subtree, none exists in the right either — so going left is safe. Either way one child can be discarded outright.Two intervals i and j overlap exactly when i.low ≤ j.high and j.low ≤ i.high. The interval trichotomy the chapter states is that exactly one of three holds: they overlap, i is entirely left of j, or i is entirely right of j.
| Structure | Base | Augmentation | New operation | Cost |
|---|---|---|---|---|
| Order-statistic tree | Red-black tree | size | OS-SELECT, OS-RANK | O(lg n) |
| Interval tree | Red-black tree | max endpoint | INTERVAL-SEARCH | O(lg n) |
O(lg n), and they compute the number of inversions in a sequence. Interval trees back calendar conflict detection, IP range and firewall rule matching, and genome annotation lookups. Both are one field away from a structure you already have.x is computable from x, x.left, and x.right, it can be maintained during insert and delete with no asymptotic cost.O(lg n) ancestors, and each rotation needs only O(1) local recomputation.Θ(n) values and the theorem does not apply.size. OS-SELECT binary-searches on rank; OS-RANK walks up, adding a parent’s left subtree whenever it comes up from the right.low, + max high endpoint. INTERVAL-SEARCH descends once because x.left.max proves one child can be discarded.Chapter 18 changes the assumption underneath every tree so far. B-trees are balanced search trees designed for data that lives on disk, where a single access costs far more than any amount of computation. The answer is nodes with hundreds of children, so the tree is only a few levels deep and a search costs a handful of disk reads.