Predecessor problem

In computer science, the predecessor problem involves maintaining a set of items to, given an element, efficiently query which element precedes or succeeds that element in an order. 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.

Definition

The problem consists of maintaining a set S, which a subset of U integers. Each of these integers can be stored with a word size of w, implying that $U\leq 2^{w}$. Data structures that solve the problem support these operations:

• predecessor(x), which returns the largest element in S less than or equal to x
• successor(x), which returns the smallest element in S greater than or equal to x

In addition, data structures which solve the dynamic version of the problem also support these operations:

• insert(x), which adds x to the set S
• delete(x), which removes x from the set S

The problem is typically analyzed in a transdichotomous model of computation such as word RAM.

Data structures

One simple solution to this problem is to use a balanced binary search tree, which achieves (in Big O notation) a running time of $O(\log n)$ for predecessor queries. The Van Emde Boas tree achieves a query time of $O(\log \log U)$, but requires $O(U)$ space.

Dan Willard proposed an improvement on this space usage with the x-fast trie, which requires $O(n\log U)$ space and the same query time, and the more complicated y-fast trie, which only requires $O(n)$ space.

See also

• Integer sorting
• y-fast trie
• Fusion tree