17.1 · Dynamic Order Statistics
Each node stores size = |subtree|. Then OS-SELECT and OS-RANK both run in O(log n).
idle
| Operation | Time | Space |
|---|---|---|
| OS-SELECT(x, k) | O(log n) | O(1) |
| OS-RANK(T, x) | O(log n) | O(1) |
| maintain size on insert/delete | O(1) extra | 1 int / node |
With subtree sizes, rank and select are inverses of each other. The key identity is r = size(left) + 1 — the rank of a node inside its subtree. Insertion and deletion update size on the way back up along the O(log n) search path, so augmentation costs nothing asymptotically.
17.2 · How to Augment a Data Structure
A four-step recipe — each step is a proof obligation.
Choose the underlying structure
Usually a red-black tree — O(log n) ops give us the budget to maintain extra fields.
Add the extra information
e.g. size for order stats, max for interval trees.
Verify it's maintainable
The field must be computable from the node and its children — and survive rotations in O(1).
Design the new operations
SELECT, RANK, INTERVAL-SEARCH — use the augmented field to prune the search path.
The red-black property is what makes augmentation cheap: every modification touches O(log n) nodes, and each touched node can recompute its extra field in O(1) from its children. That is why size and max are such natural augmentations — they are local functions of (node, left, right).
17.3 · Interval Trees
Keyed by low endpoint · each node stores max = max high in subtree.
interval axis
idle
| Operation | Time | Space |
|---|---|---|
| INTERVAL-SEARCH | O(log n) | O(1) |
| insert / delete interval | O(log n) | O(1) |
| store n intervals | — | O(n) |
The trick is the max field. At a node, if the left subtree's max is at least the query's low, an overlap must exist in the left subtree — otherwise we skip it in O(1). That is what gives the O(log n) bound: at each level we discard one subtree entirely.
18 · B-Trees (minimum degree t = 2)
Every node holds 1–3 keys. Splits, borrows and merges keep the tree perfectly balanced with all leaves at the same depth.
idle
| Operation | Time | Space |
|---|---|---|
| search | O(log_t n) | O(1) |
| insert (split on the way down) | O(log_t n) | O(1) |
| delete (borrow / merge) | O(log_t n) | O(1) |
With degree t the height is h ≤ log_t((n+1)/2) — much shorter than a binary tree, which is why B-trees are the standard on-disk index. Both insert and delete are pre-emptive: full children are split on the way down, and thin children (t−1 keys) are filled by borrowing or merging before descending, so no recursive call ever has to unwind.
19.2 · Linked-List Representation
Each set is a linked list. UNION concatenates and rewrites every element's representative pointer.
idle
| Operation | Naive | Weighted union |
|---|---|---|
| MAKE-SET | O(1) | O(1) |
| FIND | O(1) | O(1) |
| UNION | O(n) | O(n) worst, O(1) amortized |
The weighted-union heuristic — always append the shorter list to the longer — makes each element's representative pointer change at most log₂ n times, because each change at least doubles the size of the set it belongs to. Total cost over m ops is O(m + n log n).
19.3–19.4 · Disjoint-Set Forest · union by rank + path compression
Two heuristics together give the inverse-Ackermann bound — effectively O(1) for any practical n.
idle
| Heuristic | m operations | Space |
|---|---|---|
| none (naive forest) | O(m log n) | O(n) |
| union by rank only | O(m log n) | O(n) |
| + path compression | O(m·α(n)) | O(n) |
Union by rank keeps tree height O(log n): always attach the shorter tree under the taller one. Path compression flattens the path during every FIND. Together, the amortized cost per operation is α(n) — the inverse Ackermann function. For any n that fits in the universe, α(n) ≤ 4, so it behaves like a constant.