Improved Data Structures for Predecessor Queries in Integer Sets

We consider the problem of maintaining a dynamic ordered set of n integers in the range 0 : : 2^w - 1, under the operations of insertion, deletion and predecessor queries, on a unit-cost RAM with a word length of w bits. We show that all the operations above can be performed in O(min{log w, 1 log n/log w}) expected time, assuming the updates are oblivious, i.e., independent of the random choices made by the data structure. This improves upon the (deterministic) running time of O(min{log w, sqrt log n}) obtained by Fredman and Willard. We also give a very simple deterministic data structure which matches the bound of Fredman and Willard. Finally, from the randomized data structure we are able to derive improved deterministic data structures for the static version of this problem