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.[1]
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.
The problem consists of maintaining a set, which contains a subset of integers. Each of these integers can be stored with a word size of, implying that
U\le2w
predecessor(x)
, which returns the largest element in less than or equal tosuccessor(x)
, which returns the smallest element in greater than or equal toIn addition, data structures which solve the dynamic version of the problem also support these operations:
insert(x)
, which adds to the setdelete(x)
, which removes from the setThe problem is typically analyzed in a transdichotomous model of computation such as word RAM.
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(logn)
O(loglogU)
O(U)
O(nlogU)
O(n)
O(logwn)
O(n)
O(logwn+loglogn)
O(logwn)
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, there exists a value of with query time (in Big Theta notation)
\Omega\left(\tfrac{logw}{loglogw}\right)
\Omega\left(\sqrt{\tfrac{logn}{loglogn}}\right)
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:[7]