Encyclopedia

Predecessor problem

Query of largest element in a set less than an element

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated October 23, 2024

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.

The predecessor problem is a simple case of the nearest neighbor problem, and data structures that solve it have applications in problems like integer sorting.

01Definition

The problem consists of maintaining a set S, which contains 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 strictly smaller than x
successor(x), which returns the smallest element in S strictly greater than 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.

02Data 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. Fusion trees, introduced by Michael Fredman and Willard, achieve $O(\log _{w}n)$ query time and $O(n)$ for predecessor queries for the static problem. The dynamic problem has been solved using exponential trees with $O(\log _{w}n+\log \log n)$ query time, and with expected time $O(\log _{w}n)$ using hashing.

03Mathematical properties

There have been a number of papers proving lower bounds on the predecessor problem, or identifying what the running time of asymptotically optimal solutions would be. For example, Michael Beame and Faith Ellen proved that for all values of w, there exists a value of n with query time (in Big Theta notation) $\Omega \left({\tfrac {\log w}{\log \log w}}\right)$ , and similarly, for all values of n, there exists a value of n such that the query time is $\Omega \left({\sqrt {\tfrac {\log n}{\log \log n}}}\right)$ . Other proofs of lower bounds include the notion of communication complexity.

For the static predecessor problem, Mihai Pătrașcu and Mikkel Thorup showed the following lower bound for the optimal search time, in the cell-probe model: $O(1)\min \left\{{\begin{array}{l}\log _{w}n\\\lg {\frac {\ell -\lg n}{a}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left({\frac {a}{\lg n}}\,\cdot \,\lg {\frac {\ell }{a}}\right)}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left(\lg {\frac {\ell }{a}}\right/\left.\lg {\frac {\lg n}{a}}\right)}}\end{array}}\right.$ where the RAM has word length $w$ , the set contains $n$ integers of $\ell$ bits each and is represented in the RAM using $S$ words of space, and defining $a=\lg {\frac {S}{n}}+\lg w$ .

In the case where $w=\ell =\gamma \lg n$ for $\gamma >1$ and $S=n\cdot \lg ^{O(1)}n$ , the optimal search time is $\Theta (\lg \ell )$ and the van Emde Boas tree achieves this bound.

Watch videos about Predecessor problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Predecessor problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Xfast trie example.svg by Cdb273, Public domain

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Predecessor problem

01Definition

02Data structures

03Mathematical properties

Sources and credits

Related topics

Integer sorting

Y-fast trie

Fusion tree