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. The original van Emde Boas structure had size
,
so was impractical for large integers.
The
and
data structures were discovered by
Willard [62]. The
structure is very closely related
to van Emde Boas trees. One view of this is that the hash tables in an
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 [24]. This structure can store
-bit integers in
space so that the
operation runs in
time. By using a fusion tree when
and a
when
one obtains an
space data structure that can implement the
operation
in
time. Recent lower-bound results of P
tra
cu
and Thorup [48] show that these results are optimal, at least for
structures that use only
space.
opendatastructures.org