Fixed -universe successor problem Goal: maintain a dynamic subset s of size n of the universe 0=10, 1,.,u-1 of size u subject to these operations INSERT(X∈U\S): Add x to s DELETE(X E S): Remove x from S SUCCESSOR( E U): Find the next element in S larger than any element x of the universe U PREDECESSOR(XE U): Find the previous element in s smaller than x c 2001 by erik D. Demaine Introduction to Algorithms Day 23 L12.2© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.2 Fixed-universe successor problem Goal: Maintain a dynamic subset S of size n of the universe U = {0, 1, …, u – 1} of size u subject to these operations: • INSERT(x ∈ U \ S): Add x to S. • DELETE(x ∈ S): Remove x from S. • SUCCESSOR(x ∈ U): Find the next element in S larger than any element x of the universe U. • PREDECESSOR(x ∈ U): Find the previous element in S smaller than x