# 13.4 Discussion and Exercises

The first data structure to provide time , , and 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 , making it impractical for large integers.

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

Another structure for storing integers is Fredman and Willard's fusion trees [32]. This structure can store -bit integers in space so that the operation runs in time. By using a fusion tree when and a YFastTrie when , one obtains an space data structure that can implement the operation in 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 space.

Exercise 13..1   Design and implement a simplified version of a BinaryTrie that does not have a linked list or jump pointers, but for which

still runs in time.

Exercise 13..2   Design and implement a simplified implementation of an XFastTrie that doesn't use a binary trie at all. Instead, your implementation should store everything in a doubly-linked list and hash tables.

Exercise 13..3   We can think of a BinaryTrie as a structure that stores bit strings of length in such a way that each bitstring is represented as a root to leaf path. Extend this idea into an SSet implementation that stores variable-length strings and implements , , and in time proporitional to the length of .

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

Exercise 13..4   For an integer , let denote the difference between and the value returned by [if returns , then define as ]. For example, if returns 43, then .
1. Design and implement a modified version of the operation in an XFastTrie that runs in expected time. Hint: The hash table contains all the values, , such that , so that would be a good place to start.
2. Design and implement a modified version of the operation in an XFastTrie that runs in expected time.

opendatastructures.org