# 13: Data Structures for Integers

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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.

This page titled 13: Data Structures for Integers is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin (Athabasca University Press) .