# 13: Data Structures for Integers

- Page ID
- 8489

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.