Y-fast trie
| Y-fast trie | |
|---|---|
| Type | Trie |
| Invented | 1982 |
| Invented by | Dan Willard |
| Asymptotic complexity in big O notation |
|
| Space | O(n) |
| Search | O(log log M) |
| Insert | O(log log M) |
| Delete | O(log log M) |
In computer science, a y-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time O(log log M), using O(n) space, where n is the number of stored values and M is the maximum value in the domain. The structure was proposed by Dan Willard in 1982 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 keys are divided into groups of O(log M) consecutive elements and for each group a balanced binary search tree is created. To facilitate efficient insertion and deletion, each group contains at least (log M)/4 and at most 2 log M elements. For each balanced binary search tree a representative r is chosen. These representatives are stored in the x-fast trie. A representative r need not be an element of the tree associated with it, but it does need be an integer smaller than the successor of r and the minimum element of the tree associated with that successor and greater than the predecessor of r and the maximum element of the tree associated with that predecessor. Initially, the representative of a tree will be an integer between the minimum and maximum element in its tree.
Since the x-fast trie stores O(n / log M) representatives and each representative occurs in O(log M) hash tables, this part of the y-fast trie uses O(n) space. The balanced binary search trees store n elements in total which uses O(n) space. Hence, in total a y-fast trie uses O(n) space.
Like van Emde Boas trees and x-fast tries, y-fast tries support the operations of an ordered associative array. This includes the usual associative array operations, along with two more order operations, Successor and Predecessor:
A key k can be stored in either the tree of the smallest representative r greater than k or in the tree of the predecessor of r since the representative of a binary search tree need not be an element stored in its tree. Hence, one first finds the smallest representative r greater than k in the x-fast trie. Using this representative, one retrieves the predecessor of r. These two representatives point to two balanced binary search trees, which one both searches for k.
...
Wikipedia