Chapter 14 - Augmenting Data Structures

Chapter 14 explains how to attach auxiliary information to a data structure and maintain enough local consistency to support stronger queries. The first CLRS-Lean pass formalizes the mathematical core of order-statistic trees: each node stores a subtree size, and rank selection uses the left-subtree size to choose a branch. The rotation layer now exposes cached-root-size preservation, ideal rank-selection preservation, and the corresponding augmented-selector wrapper for well-sized trees. It also exposes a recompute-then-rotate bridge: from any tree, recomputing size fields before a local rotation produces a well-sized tree whose augmented selector still agrees with the original ideal rank selector.

Sections

• 14.1 Order-statistic trees: partial at the complete fourth-edition dynamic-order-statistics interface. Main results: CLRS.Chapter14.OSTree.storedSize_eq_realSize_of_wellSized, CLRS.Chapter14.OSTree.recomputeSizes_wellSized, CLRS.Chapter14.OSTree.keys_recomputeSizes, and CLRS.Chapter14.OSTree.keys_rotateLeft, CLRS.Chapter14.OSTree.keys_rotateRight, CLRS.Chapter14.OSTree.realSize_rotateLeft, CLRS.Chapter14.OSTree.realSize_rotateRight, CLRS.Chapter14.OSTree.storedSize_rotateLeft_of_wellSized, CLRS.Chapter14.OSTree.storedSize_rotateRight_of_wellSized, CLRS.Chapter14.OSTree.rankSelect?_rotateLeft, CLRS.Chapter14.OSTree.rankSelect?_rotateRight, CLRS.Chapter14.OSTree.rotateLeft_wellSized, CLRS.Chapter14.OSTree.rotateRight_wellSized, and CLRS.Chapter14.OSTree.osSelect?_eq_rankSelect?_of_wellSized, CLRS.Chapter14.OSTree.osSelect?_rotateLeft_eq_rankSelect?_of_wellSized, CLRS.Chapter14.OSTree.osSelect?_rotateRight_eq_rankSelect?_of_wellSized, CLRS.Chapter14.OSTree.realSize_recomputeSizes, CLRS.Chapter14.OSTree.rankSelect?_recomputeSizes, CLRS.Chapter14.OSTree.rotateLeft_recomputeSizes_wellSized, CLRS.Chapter14.OSTree.rotateRight_recomputeSizes_wellSized, CLRS.Chapter14.OSTree.osSelect?_rotateLeft_recomputeSizes_eq_rankSelect?, and CLRS.Chapter14.OSTree.osSelect?_rotateRight_recomputeSizes_eq_rankSelect?. The size augmentation is now also threaded through an executable red-black insertion on the colour-and-size augmented tree CLRS.Chapter14.OSRBTree: CLRS.Chapter14.OSRBTree.wellSized_insert, CLRS.Chapter14.OSRBTree.storedSize_insert, CLRS.Chapter14.OSRBTree.osSelect?_insert_eq_rankSelect?, CLRS.Chapter14.OSRBTree.toRB_insert, CLRS.Chapter14.OSRBTree.redBlackShape_toRB_insert, and CLRS.Chapter14.OSRBTree.mem_keys_insert.

• 14.3 Interval trees: partial at the complete fourth-edition interface; the static functional well-augmented BST search model is proved. Main results: CLRS.Chapter14.IntervalTree.intervalSearch?_some_overlap, CLRS.Chapter14.IntervalTree.intervalSearch?_none_noOverlap, and CLRS.Chapter14.IntervalTree.intervalSearch?_spec. It also packages the general augmentation interface: an arbitrary augmentation threaded through an executable red-black insertion on the generic CLRS.Chapter14.AugmentedRBTree, with CLRS.Chapter14.AugmentedRBTree.wellAugmented_insert, CLRS.Chapter14.AugmentedRBTree.toRB_insert, CLRS.Chapter14.AugmentedRBTree.redBlackShape_toRB_insert, CLRS.Chapter14.AugmentedRBTree.mem_keys_insert, CLRS.Chapter14.AugmentedRBTree.wellAugmented_delete, and CLRS.Chapter14.AugmentedRBTree.toRB_delete, and the size and interval instances CLRS.Chapter14.AugmentedRBTree.sizeAug_wellAugmented_insert and CLRS.Chapter14.AugmentedRBTree.maxHighAug_wellAugmented_insert.

Current Gaps

The current model proves size-field preservation, OS-SELECT's agreement with an inorder selector, the local generic augmentation invariant, and static interval-search correctness. It also threads arbitrary cached fields through functional red-black insertion and deletion. The full fourth-edition boundary still lacks OS-RANK; combined BST/red-black/augmentation preservation; the constant-time-combine-to-logarithmic-operation cost theorem; and a bridge connecting interval-specific updates on the dynamic augmented red-black type to the static interval-search model. The interval comparison also needs a policy for equal low endpoints before it represents arbitrary interval sets.