Data structure maintenance Q. Why not keep the ranks themselves in the nodes instead of subtree sizes? A. They are hard to maintain when the red-black tree is modified Modifying operations: INSERT and delete Strategy: update subtree sizes when inserting or deleting c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 L11.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.6 Data structure maintenance Q. Why not keep the ranks themselves in the nodes instead of subtree sizes? A. They are hard to maintain when the red-black tree is modified. Modifying operations: INSERT and DELETE. Strategy: Update subtree sizes when inserting or deleting
Example of insertion INSERT( K) A T c 2001 by Charles E Leiserson Introduction to Agorithms Day20L11.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.7 Example of insertion M 9 M 9 C 5 C 5 A 1 A 1 F 3 F 3 N 1 N 1 Q 1 Q 1 P 3 P 3 H 1 H 1 D 1 D 1 INSERT(“K”) M 10 M 10 C 6 C 6 F 4 F 4 H 2 H 2 K 1 K 1
Handling rebalancing Dont forget that RB-INSERT and RB-DELETE may also need to modify the red-black tree in order to maintain balance Recolorings: no effect on subtree sizes Rotations: fix up subtree sizes in O(1)time Example:/E 16 RB-INSERT and rb-delete still run in odg n) time c 2001 by Charles E Leiserson Introduction to Algorithms Day 20 Lll. 8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.8 Handling rebalancing Don’t forget that RB-INSERT and RB-DELETE may also need to modify the red-black tree in order to maintain balance. • Recolorings: no effect on subtree sizes. • Rotations: fix up subtree sizes in O(1) time. Example: C 11 C 11 E 16 E 16 7 3 4 C 16 C 16 E 8 E 8 7 3 4 ∴RB-INSERT and RB-DELETE still run in O(lg n) time
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 (redblack 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 (RBINSERT, 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