Y-fast trie

In computer science, a y-fast trie is a data structure for storing integers from a bounded domain.

The structure was proposed by Dan Willard in 1982[1] to decrease the O(n log M) space used by an x-fast trie.

A y-fast trie consists of two data structures: the top half is an x-fast trie and the lower half consists of a number of balanced binary trees.

The balanced binary search trees store n elements in total which uses O(n) space.

Like van Emde Boas trees and x-fast tries, y-fast tries support the operations of an ordered associative array.

These two representatives point to two balanced binary search trees, which one searches for the successor of k.[3] Finding the smallest representative r greater than k in the x-fast trie takes O(log log M) time and using r to find its predecessor takes constant time.

[1] Searching for the predecessor of a key k is highly similar to finding its successor.

Finally, inserting and deleting the three representatives takes O(log M) time.

However, since one splits the tree at most once every O(log M) insertions and deletions, this takes constant amortized time.

Merging and possibly splitting the balanced binary search tree, however, is done at most once for every O(log M) insertions and deletions.