Data-structure augmentation Methodology:(e.g, order-statistics trees) 1. Choose an underlying data structure(red- black trees) 2. Determine additional information to be stored in the data structure (subtree sizes) 3. Verify that this information can be maintained for modifying operations(RB INSERT, RB-DELETE--don't forget rotations) 4. Develop new dynamic-set operations that use the information(OS-SELECT and OS-RANK) The ese steps are guidelines, not rigid rules c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 Ll1.9© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.9 Data-structure augmentation Methodology: (e.g., order-statistics trees) 1. Choose an underlying data structure (red￾black trees). 2. Determine additional information to be stored in the data structure (subtree sizes). 3. Verify that this information can be maintained for modifying operations (RB￾INSERT, RB-DELETE — don’t forget rotations). 4. Develop new dynamic-set operations that use the information (OS-SELECT and OS-RANK). These steps are guidelines, not rigid rules