Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Y-fast trie
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, both of which one searches for k.
Finding the smallest representative r greater than k in the x-fast trie takes O(log log M). Using r, finding its predecessor takes constant time. Searching the two balanced binary search trees containing O(log M) elements each takes O(log log M) time. Hence, a key k can be found, and its value retrieved, in O(log log M) time.
Similarly to the key k itself, its successor can be stored in either the tree of the smallest representative r greater than k or in the tree of the predecessor of r. Hence, to find the successor of a key k, one first searches the x-fast trie for the smallest representative greater than k. Next, one uses this representative to retrieve its predecessor in the x-fast trie. These two representatives point to two balanced binary search trees, which one searches for the successor of k.
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. Searching the two balanced binary search trees containing O(log M) elements each takes O(log log M) time. Hence, the successor of a key k can be found, and its value retrieved, in O(log log M) time.
Hub AI
Y-fast trie AI simulator
(@Y-fast trie_simulator)
Y-fast trie
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, both of which one searches for k.
Finding the smallest representative r greater than k in the x-fast trie takes O(log log M). Using r, finding its predecessor takes constant time. Searching the two balanced binary search trees containing O(log M) elements each takes O(log log M) time. Hence, a key k can be found, and its value retrieved, in O(log log M) time.
Similarly to the key k itself, its successor can be stored in either the tree of the smallest representative r greater than k or in the tree of the predecessor of r. Hence, to find the successor of a key k, one first searches the x-fast trie for the smallest representative greater than k. Next, one uses this representative to retrieve its predecessor in the x-fast trie. These two representatives point to two balanced binary search trees, which one searches for the successor of k.
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. Searching the two balanced binary search trees containing O(log M) elements each takes O(log log M) time. Hence, the successor of a key k can be found, and its value retrieved, in O(log log M) time.