---
title: Predecessor problem
slug: predecessor-problem
qid: 
snapshot: enwiki-001252903150
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1252903150
tags: [20363771, 23603337, 23617853, 29113383]
---

# Predecessor problem

> [!note] Provenance
> Snapshot `enwiki-001252903150` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1252903150> · Licensed CC BY-SA 4.0

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.

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. 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.
