13: Data Structures for Integers

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 $$\mathtt{w}$$-bit integers. That is, we want to implement $$\mathtt{add(x)}$$, $$\mathtt{remove(x)}$$, and $$\mathtt{find(x)}$$ where $$\mathtt{x}\in\{0,\ldots,2^{\mathtt{w}}-1\}$$. 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 $$O(\mathtt{w})$$ time. This is not very impressive, since any subset of $$\{0,\ldots,2^{\mathtt{w}}-1\}$$ has size $$\mathtt{n}\le 2^{\mathtt{w}}$$, so that $$\log \mathtt{n} \le \mathtt{w}$$. All the other SSet implementations discussed in this book perform all operations in $$O(\log \mathtt{n})$$ 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 $$\mathtt{find(x)}$$ operation runs in $$O(\log \mathtt{w})$$ time. However, $$\mathtt{add(x)}$$ and $$\mathtt{remove(x)}$$ operations in an XFastTrie still take $$O(\mathtt{w})$$ time and the space used by an XFastTrie is $$O(\mathtt{n}\cdot\mathtt{w})$$.

The third data structure, the YFastTrie, uses an XFastTrie to store only a sample of roughly one out of every $$\mathtt{w}$$ elements and stores the remaining elements in a standard SSet structure. This trick reduces the running time of $$\mathtt{add(x)}$$ and $$\mathtt{remove(x)}$$ to $$O(\log \mathtt{w})$$ and decreases the space to $$O(\mathtt{n})$$.

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 $$\mathtt{ix}$$ is always the integer value associated with $$\mathtt{x}$$, and the method $$\texttt{in.}$$$$\mathtt{intValue(x)}$$ converts $$\mathtt{x}$$ to its associated integer. In the text, however, we will simply treat $$\mathtt{x}$$ as if it is an integer.