Discussion on Data Structures for Integers

Discover more aspects regarding XFastTrie and YFastTrie.

We'll cover the following

Additional notes

The first data structure to provide O(logw)O(\log w) time add(x), remove(x), and find(x) operations was proposed by van Emde Boas and has since become known as the van Emde BoasP. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett., 6(3):80–82, 1977. (or stratified) tree. The original van Emde Boas structure had size 2w2^w, making it impractical for large integers.

The XFastTrie and YFastTrie data structures were discovered by WillardD. E. Willard. Log-logarithmic worst-case range queries are possible in space Θ(N). Inf. Process. Lett., 17(2):81–84, 1983.. 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 t[i]t[i], a van Emde Boas tree stores an array of length 2i2^i.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy