Chapter 17: Augmenting Data Structures

The chapter formalizes this through a four-step process: choose a base structure, decide what extra information to maintain, verify that basic operations can update that information efficiently, and develop new operations that exploit it — with Theorem 17.1 providing a key guarantee that if an augmented attribute depends only on a node and its children and can be computed in O(1) time, then insertions and deletions remain O(log n). The primary application is the order-statistic tree, which augments a red-black tree by storing a size attribute at each node representing the number of nodes in its subtree, enabling two new operations: OS-SELECT, which finds the ith smallest element by comparing i to the current node's rank and recursing into the appropriate subtree in O(log n) time, and OS-RANK, which computes a node's position in the sorted order by accumulating left subtree sizes while climbing toward the root, also in O(log n) time — with size attributes kept consistent during insertions, deletions, and rotations at O(log n) and O(1) cost respectively. The chapter's second major application is the interval tree, which stores intervals keyed by their low endpoints and augments each node with a max attribute recording the highest endpoint in its subtree, maintained as x.max = max(x.int.high, x.left.max, x.right.max) and updated in O(1) during rotations. The INTERVAL-SEARCH operation navigates the tree by going left when the left subtree's max is at least the query interval's low endpoint and right otherwise, terminating at the first overlapping interval or an empty subtree — proven correct by interval trichotomy — in O(log n) time.