Next: 13.1 BinaryTrie: A digital Up: Open Data Structures (in Previous: 12.4 Discussion and Exercises Contents Index
In this chapter, we return to the problem of implementing an SSet.
The difference now is that we assume the elements stored in the SSet are
-bit integers. That is, we want to implement
,
,
and
where
. It is not too hard
to think of plenty of applications where the data--or at least the key
that we use for sorting the data--is an integer.
We will discuss three data structures, each building on the ideas of
the previous. The first structure, the BinaryTrie performs all three
SSet operations in
time. This is not very impressive, since
any subset of
has size
, so that
. All the other SSet implementations discussed in
this book perform all operations in
time so they are all
at least as fast as a BinaryTrie.
The second structure, the XFastTrie, speeds up the search in a
BinaryTrie by using hashing. With this speedup, the
operation runs in
time. However,
and
operations in an XFastTrie still take
time and the space used
by an XFastTrie is
.
The third data structure, the YFastTrie, uses an XFastTrie to store
only a sample of roughly one out of every
elements and stores the
remaining elements in a standard SSet structure. This trick reduces the
running time of
and
to
and decreases
the space to
.
The implementations used as examples in this chapter can store any type of
data, as long as an integer can be associated with it. In the code samples,
the variable
is always the integer value associated with
, and the method
converts
to its associated integer. In
the text, however, we will simply treat
as if it is an integer.