Predecessor problem

In computer science, the predecessor problem involves maintaining a totally ordered set of items to, given an element, efficiently query which element precedes or succeeds that element in an order. The problem is analyzed in a transdichotomous model of computation such as word RAM, so the set is typically a subset of U integers, each of which has a word size of w. Data structures used to solve the problem include balanced binary search trees, Van Emde Boas trees, and fusion trees. In the static predecessor problem, the set of elements does not change, but in the dynamic predecessor problem, insertions into and deletions from the set are allowed.