Selection Implementation trick: Use a sentinel (dummy record) for NIL such that sizeNIL]=0 OS-SELECT(x, 1)b ith smallest element in the subtree rooted at x k<size left+1 bk=rank(x) if i=k then return x if i<k then return os-select(left, 1) else return OS-SELECT(right i-k) (OS-RANk is in the textbook c 2001 by Charles E Leiserson Introduction to Agorithms Day 20 Lll.4© 2001 by Charles E. Leiserson Introduction to Algorithms Day 20 L11.4 Selection OS-SELECT(x, i) ⊳ ith smallest element in the subtree rooted at x k ← size[left[x]] + 1 ⊳ k = rank(x) if i = k then return x if i < k then return OS-SELECT(left[x], i) else return OS-SELECT(right[x], i – k ) Implementation trick: Use a sentinel (dummy record) for NIL such that size[NIL] = 0. (OS-RANK is in the textbook.)