Predecessor Problem Predecessor Problem

• The predecessor problem: Maintain a set S ⊆ U = {0,..., u-1} under operations • predecessor(x): return the largest element in S that is ≤ x. • sucessor(x): return the smallest element in S that is ≥ x. • insert(x): set S = S ∪ {x} • delete(x): set S = S- {x} • We often ignore successor since we can get it from predecessor. 0 u-1 xpredecessor(x) successor(x) Applications • What applications do we know? • Simplest version of nearest neighbor problem. • Several applications in other algorithms and data structures. • Probably most practically solved problem in the world: Out all computational resources globally most are used used to solve the predecessor problem