Next: Bibliography Up: 13. Data Structures for Previous: 13.3 : A Doubly-Logarithmic Contents
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
![$ \mathtt{t[i]}$](img683.png){kind=small}
, 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.
that
doesn't have a linked list or jump pointers, but can still do find(x)
in O(w) time.
that doesn't use a binary trie at all. Instead, you implementation
should store everything is stored in a doubly-linked list and
hash tables.
, let
be the difference between
and the
value returned by
[if
returns
, then define
. Design and implement a modified version of
the
operation in an
that runs in
expected time.
opendatastructures.org