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