E xample OS- SELECT(root, 5) k=6 i=5 k=2 A k 32 k=1 Running time=O(h)=o(g n) for red-black trees c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 L11. 5© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.5 Example 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 OS-SELECT(root, 5) i = 5 k = 6 M 9 M 9 C 5 C 5 i = 5 k = 2 i = 3 k = 2 F 3 F 3 i = 1 k = 1 H 1 H 1 Running time = O(h) = O(lg n) for red-black trees