Partial Integers

Bits as part of integers

In this module, we return to the problem of implementing an SSet. The difference now is that we assume the elements stored in the SSet are $w$-bit integers. That is, we want to implement add(x), remove(x), and find(x) where $x \in \{0,...,2^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’ll discuss three data structures, each building on the ideas of the previous. The first structure, the BinaryTrie performs all three SSet operations in $O(w)$ time. This is not very impressive, since any subset of $\{0,...,2^w − 1\}$ has size $n \leq 2^w$ ...