Chapter 17: Augmented Data Structures – Order Stats, Interval Trees | Introduction to Algorithms

Chapter 17 introduces the concept of augmented data structures — existing structures enhanced with additional information to support more powerful operations without increasing asymptotic complexity. The chapter focuses on augmenting red-black trees to implement order-statistic trees and interval trees, providing O(log n) performance for advanced queries like finding ranks and overlapping intervals.

✅ Order Statistic Trees
🔸 Augments red-black trees with a size attribute for each node
🔸 Maintains O(log n) performance for dynamic sets and rank-based queries

🔸 OS-SELECT(x, i)
 🔸 Returns the ith smallest element in subtree rooted at x
 🔸 Recursively compares i to rank of current node
 🔸 Time: O(log n)

🔸 OS-RANK(T, x)
 🔸 Computes rank of node x in tree T
 🔸 Adds sizes of left subtrees while climbing up
 🔸 Time: O(log n)

🔸 Maintaining size during updates
 🔸 Insertion: increment sizes on path to new node, O(log n)
 🔸 Deletion: decrement sizes on path from removed node up, O(log n)
 🔸 Rotations: update size attributes in O(1) time per rotation

✅ How to Augment a Data Structure
🔸 General four-step process for augmentation:
 🔸 Choose a suitable base structure (e.g., red-black tree)
 🔸 Decide what extra info to maintain (e.g., size or max)
 🔸 Verify basic operations can efficiently update new info
 🔸 Develop new operations that use the added information

🔸 Theorem 17.1
 🔸 If augmented attribute f(x) depends only on x and its children, and can be computed in O(1) time, then insertions and deletions still run in O(log n)

✅ Interval Trees
🔸 Used to store and query intervals [low, high]
🔸 Tree is keyed by low endpoints of intervals
🔸 Each node x stores:
🔸 Tree remains a red-black tree and satisfies all red-black invariants

🔸 Maintaining max during updates
 🔸 Update max attributes during rotations in O(1) time
 🔸 Insertions and deletions remain O(log n)

🔸 INTERVAL-SEARCH(T, i)
 🔸 Returns node with interval overlapping query i or NIL
 🔸 Stops on first overlap or when subtree is empty
 🔸 Time: O(log n)

🔸 Correctness (Theorem 17.2)
 🔸 Search always moves toward a subtree where overlap may exist
 🔸 Uses interval trichotomy to guarantee correctness

📚 Glossary of Key Terms
🔸 Augmented Data Structure – A structure with added fields for extended functionality
🔸 Order Statistic – The ith smallest element in a set
🔸 Rank – Position of an element in the sorted order
🔸 Order-Statistic Tree – Red-black tree augmented with subtree sizes
🔸 Interval – Closed range [low, high]
🔸 Interval Tree – Red-black tree keyed by interval low endpoints, augmented with max high endpoint
🔸 INTERVAL-SEARCH – Finds a node with overlapping interval in O(log n)
🔸 Interval Trichotomy – For any two intervals, one of: they overlap, one ends before the other begins