Engineering Predecessor Data Structures for Dynamic Integer Sets

Patrick Dinklage, Johannes Fischer, Alexander Herlez

We present highly optimized data structures for the dynamic predecessor problem, where the task is to maintain a set $S$ of $w$-bit numbers under insertions, deletions, and predece…