13.4 Discussion and Exercises

The first data structure to provide $O(\log\ensuremath{\mathtt{w}})$ time $\mathtt{add(x)}$, $\mathtt{remove(x)}$, and $\mathtt{find(x)}$ operations was proposed by van Emde Boas and has since become known as the van Emde Boas (or stratified) tree [72]. The original van Emde Boas structure had size $2^{\ensuremath{\mathtt{w}}}$, making it impractical for large integers.

The $\mathtt{XFastTrie}$ and $\mathtt{YFastTrie}$ data structures were discovered by Willard [75]. The $\mathtt{XFastTrie}$ structure is closely related to van Emde Boas trees; for instance, the hash tables in an $\mathtt{XFastTrie}$ replace arrays in a van Emde Boas tree. That is, instead of storing the hash table $\mathtt{t[i]}$, a van Emde Boas tree stores an array of length $2^{\ensuremath{\mathtt{i}}}$.

Another structure for storing integers is Fredman and Willard's fusion trees [32]. This structure can store $\mathtt{n}$ $\mathtt{w}$-bit integers in $O(\ensuremath{\mathtt{n}})$ space so that the $\mathtt{find(x)}$ operation runs in $O((\log \ensuremath{\mathtt{n}})/(\log \ensuremath{\mathtt{w}}))$ time. By using a fusion tree when $\log \ensuremath{\mathtt{w}} > \sqrt{\log \ensuremath{\mathtt{n}}}$ and a $\mathtt{YFastTrie}$ when $\log \ensuremath{\mathtt{w}} \le \sqrt{\log \ensuremath{\mathtt{n}}}$, one obtains an $O(\ensuremath{\mathtt{n}})$ space data structure that can implement the $\mathtt{find(x)}$ operation in $O(\sqrt{\log \ensuremath{\mathtt{n}}})$ time. Recent lower-bound results of Ptracu and Thorup [57] show that these results are more or less optimal, at least for structures that use only $O(\ensuremath{\mathtt{n}})$ space.

Exercise 13..1   Design and implement a simplified version of a $\mathtt{BinaryTrie}$ that does not have a linked list or jump pointers, but for which $\mathtt{find(x)}$

still runs in $O(\ensuremath{\mathtt{w}})$ time.

Exercise 13..2   Design and implement a simplified implementation of an $\mathtt{XFastTrie}$ that doesn't use a binary trie at all. Instead, your implementation should store everything in a doubly-linked list and $\ensuremath{\mathtt{w}}+1$ hash tables.

Exercise 13..3   We can think of a $\mathtt{BinaryTrie}$ as a structure that stores bit strings of length $\mathtt{w}$ in such a way that each bitstring is represented as a root to leaf path. Extend this idea into an $\mathtt{SSet}$ implementation that stores variable-length strings and implements $\mathtt{add(s)}$, $\mathtt{remove(s)}$, and $\mathtt{find(s)}$ in time proporitional to the length of $\mathtt{s}$.

Hint: Each node in your data structure should store a hash table that is indexed by character values.

Exercise 13..4   For an integer $\ensuremath{\mathtt{x}}\in\{0,\ldots2^{\ensuremath{\mathtt{w}}}-1\}$, let $d(\ensuremath{\mathtt{x}})$ denote the difference between $\mathtt{x}$ and the value returned by $\mathtt{find(x)}$ [if $\mathtt{find(x)}$ returns $\mathtt{null}$, then define $d(\ensuremath{\mathtt{x}})$ as $2^\ensuremath{\mathtt{w}}$]. For example, if $\mathtt{find(23)}$ returns 43, then $d(23)=20$.

1. Design and implement a modified version of the $\mathtt{find(x)}$ operation in an $\mathtt{XFastTrie}$ that runs in $O(1+\log d(\ensuremath{\mathtt{x}}))$ expected time. Hint: The hash table $t[\ensuremath{\mathtt{w}}]$ contains all the values, $\mathtt{x}$, such that $d(\ensuremath{\mathtt{x}})=0$, so that would be a good place to start.
2. Design and implement a modified version of the $\mathtt{find(x)}$ operation in an $\mathtt{XFastTrie}$ that runs in $O(1+\log\log d(\ensuremath{\mathtt{x}}))$ expected time.