Overview

This chapter teaches a general methodology for extending ("augmenting") standard data structures with additional information to support new operations efficiently. Rather than designing entirely new data structures from scratch, we add attributes to existing ones and show how to maintain them during modifications. The chapter demonstrates this approach with two concrete augmented red-black trees: order-statistic trees (supporting rank queries in O(lg n)) and interval trees (supporting overlap queries in O(lg n)), and presents a general theorem (Theorem 14.1) that simplifies augmenting red-black trees.

Key Concepts

• Augmentation methodology (four steps):

1. Choose an underlying data structure (e.g., red-black tree).

2. Determine additional information to store in each node.

3. Verify that the additional information can be maintained during basic modifying operations (INSERT, DELETE) without increasing asymptotic cost.

4. Develop new operations that exploit the additional information.

• Order-statistic tree: A red-black tree augmented with a size attribute in each node x, where x.size = number of internal nodes in the subtree rooted at x (including x). The identity x.size = x.left.size + x.right.size + 1 holds, with T.nil.size = 0.
• Interval tree: A red-black tree augmented with a max attribute in each node x, where x.max = maximum endpoint of any interval stored in the subtree rooted at x. Keyed by the low endpoint of each interval. The identity x.max = max(x.int.high, x.left.max, x.right.max) holds.
• Interval trichotomy: For any two intervals i and i', exactly one holds: (a) they overlap, (b) i is entirely to the left of i', or (c) i is entirely to the right of i'.
• Theorem 14.1 (Augmenting a red-black tree): If an attribute f in each node x depends only on the information in x, x.left, and x.right (including x.left.f and x.right.f), then f can be maintained during insertion and deletion without affecting the O(lg n) performance. The key insight: changes to f propagate only upward to ancestors, and rotations affect only O(1) nodes each.

Algorithms and Techniques

Order-Statistic Operations

OS-SELECT(x, i): Retrieves the ith smallest key in the subtree rooted at x.

1. Compute r = x.left.size + 1 (the rank of x within its subtree).

2. If i = r, return x.

3. If i < r, recurse into x.left with the same i.

4. If i > r, recurse into x.right with i − r.

Each recursive call descends one level, so the running time is O(lg n).