X/Y fast tries and an open problem

Pat Morin

We consider data structures for storing integer keys in {0,...,M-1}. Hash tables support insert, delete, and exact-search operations in O(1) expected time. Several data structures, including van Emde Boas trees and Y-fast tries, support insert, delete, and successor-search operations in O(log log M) expected time.

I will show that these results can be partly unified; a variant of X-fast tries supports successor-search for a key x in O(1 + log log (|x - succ(x)|+2)) expected time. Can this structure be made dynamic so that it supports insertion and deletion in the same time bound?