The first data structure to provide time , , and operations was proposed by van Emde Boas and has since become known as the van Emde Boas (or stratified) tree [74]. The original van Emde Boas structure had size , making it impractical for large integers.

The `XFastTrie` and `YFastTrie` data structures were discovered by
Willard [77]. The `XFastTrie` structure is closely related
to van Emde Boas trees; for instance, the hash tables in an `XFastTrie`
replace arrays in a van Emde Boas tree. That is, instead of storing
the hash table
, a van Emde Boas tree stores an array of length
.

Another structure for storing integers is Fredman and Willard's fusion
trees [32].
This structure can store
-bit integers in
space so that the
operation runs in
time. By using a fusion tree when
and
a `YFastTrie` when
, one obtains an
space data structure that can implement the
operation in
time. Recent lower-bound results of Ptracu
and Thorup [59] show that these results are more or less optimal,
at least for structures that use only
space.

still runs in time.

Hint: Each node in your data structure should store a hash table that is indexed by character values.

- Design and implement a modified version of the
operation in an
`XFastTrie`that runs in expected time. Hint: The hash table contains all the values, , such that , so that would be a good place to start. - Design and implement a modified version of the
operation in an
`XFastTrie`that runs in expected time.

opendatastructures.org