{
  "id": "enwiki-001252903150",
  "slug": "predecessor-problem",
  "title": "Predecessor problem",
  "qid": "",
  "lead": "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.",
  "body": "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.",
  "categories": [
    "20363771",
    "23603337",
    "23617853",
    "29113383"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1252903150",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1729682147.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001252903150",
    "type": "webpage",
    "title": "Predecessor problem",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/predecessor-problem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001252903150",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1252903150",
    "note": "Immutable snapshot enwiki-001252903150"
  }
}