Trie

Searching a ${\displaystyle {\text{Value}}}$ in a trie is guided by the characters in the search string key, as each node in the trie contains a corresponding link to each possible character in the given string. Thus, following the string within the trie yields the associated ${\displaystyle {\text{Value}}}$ for the given string key. A ${\displaystyle {\text{nil}}}$ link within search execution indicates the inexistence of the key.[14]^: 732-733

Following pseudocode implements the search procedure for a given string key (${\displaystyle {\text{key}}}$) in a rooted trie (${\displaystyle {\text{x}}}$).[15]^: 135

Trie-Find(x, key)
    for 0 ≤ i < key.length do
        if x.Children[key[i]] = nil then
            return false
        end if
        x := x.Children[key[i]]
    repeat
    return x.Value

In the above pseudocode, ${\displaystyle {\text{x}}}$ and ${\displaystyle {\text{key}}}$ correspond to the pointer of trie's root node and the string key respectively. The search operation, in a standard trie, takes ${\displaystyle O({\text{dm}})}$, ${\displaystyle {\text{m}}}$ is the size of the string parameter ${\displaystyle {\text{key}}}$, and ${\displaystyle {\text{d}}}$ corresponds to the alphabet size.[16]^: 754 Binary search trees, on the other hand, take ${\displaystyle O(m\log n)}$ on the worst case, since the search depends on the height of the tree (${\displaystyle \log n}$) of the BST (in case of balanced trees), where ${\displaystyle {\text{n}}}$ and ${\displaystyle {\text{m}}}$ being number of keys and the length of the keys.[12]^: 358

Tries occupy less space in comparison with BST if it encompasses a large number of short strings, since nodes share common initial string subsequences and stores the keys implicitly on the structure.[12]^: 358 The terminal node of the tree contains a non-nil ${\displaystyle {\text{Value}}}$, and it is a search hit if the associated value is found in the trie, and search miss if it is not.[14]^: 733

Insertion into trie is guided by using the character sets as the indexes into the ${\displaystyle {\text{Children}}}$ array until last character of the string key is reached.[14]^: 733-734 Each node in the trie corresponds to one call of the radix sorting routine, as the trie structure reflects the execution of pattern of the top-down radix sort.[15]^: 135

1
2
3
4
5
6
7
8
9

Trie-Insert(x, key, value)
    for 0 ≤ i < key.length do
        if x.Children[key[i]] = nil then
            x.Children[key[i]] := Node()
        end if
        x := x.Children[key[i]]
    repeat
    x.Value := value
    x.Is-Terminal := True

If a ${\displaystyle {\text{nil}}}$ link is encountered prior to reaching the last character of the string key, a new ${\displaystyle {\text{Node}}}$ is created, such along lines 3–5.[14]^: 745 ${\displaystyle {\text{x.Value}}}$ gets assigned to input ${\displaystyle {\text{value}}}$; if ${\displaystyle {\text{x.Value}}}$ wasn't ${\displaystyle {\text{nil}}}$ at the time of insertion, the value associated with the given string key gets substituted with the current one.

Deletion of a key–value pair from a trie involves finding the terminal node with the corresponding string key, marking the terminal indicator and value to false and ${\displaystyle {\text{nil}}}$ correspondingly.[14]^: 740

Following is a recursive procedure for removing a string key (${\displaystyle {\text{key}}}$) from rooted trie (${\displaystyle {\text{x}}}$).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Trie-Delete(x, key)
    if key = nil then
        if x.Is-Terminal = True then
            x.Is-Terminal := False
            x.Value := nil
        end if
        for 0 ≤ i < x.Children.length
            if x.Children[i] != nil
                return x
            end if
        repeat
        return nil
    end if
    x.Children[key[0]] := Trie-Delete(x.Children[key[0]], key[1:])
    return x

The procedures begins by examining the ${\displaystyle {\text{key}}}$; ${\displaystyle {\text{nil}}}$ denotes the arrival of a terminal node or end of string key. If terminal and if it has no children, the node gets removed from the trie (line 14 assign the character index to ${\displaystyle {\text{nil}}}$). However, an end of string key without the node being terminal indicates that the key does not exist, thus the procedure does not modify the trie. The recursion proceeds by incrementing ${\displaystyle {\text{key}}}$'s index.

A trie can be used to replace a hash table, over which it has the following advantages:[12]^: 358

• Searching for a node with an associated key of size ${\displaystyle m}$ has the complexity of ${\displaystyle O(m)}$, whereas an imperfect hash function may have numerous colliding keys, and the worst-case lookup speed of such a table would be ${\displaystyle O(N)}$, where ${\displaystyle N}$ denotes the total number of nodes within the table.
• Tries do not need a hash function for the operation, unlike a hash table; there are also no collisions of different keys in a trie.
• Buckets in a trie, which are analogous to hash table buckets that store key collisions, are necessary only if a single key is associated with more than one value.
• String keys within the trie can be sorted using a predetermined alphabetical ordering.

However, tries are less efficient than a hash table when the data is directly accessed on a secondary storage device such as a hard disk drive that has higher random access time than the main memory.[6] Tries are also disadvantageous when the key value cannot be easily represented as string, such as floating point numbers where multiple representations are possible (e.g. 1 is equivalent to 1.0, +1.0, 1.00, etc.),[12]^: 359 however it can be unambiguously represented as a binary number in IEEE 754, in comparison to two's complement format.[17]

Bitwise tries are used to address the enormous space requirement for the trie nodes in a naive simple pointer vector implementations. Each character in the string key set is represented via individual bits, which are used to traverse the trie over a string key. The implementations for these types of trie use vectorized CPU instructions to find the first set bit in a fixed-length key input (e.g. GCC's __builtin_clz() intrinsic function). Accordingly, the set bit is used to index the first item, or child node, in the 32- or 64-entry based bitwise tree. Search then proceeds by testing each subsequent bit in the key.[19]

This procedure is also cache-local and highly parallelizable due to register independency, and thus performant on out-of-order execution CPUs.[19]

Radix tree, also known as a compressed trie, is a space-optimized variant of a trie in which nodes with only one child get merged with its parents; elimination of branches of the nodes with a single child results in better in both space and time metrics.[20][21]^: 452 This works best when the trie remains static and set of keys stored are very sparse within their representation space.[22]^: 3–16

One more approach is to "pack" the trie, in which a space-efficient implementation of a sparse packed trie applied to automatic hyphenation, in which the descendants of each node may be interleaved in memory.[8]

Fig. 4: Patricia tree representation of string keys: in, integer, interval, string, and structure.

Patricia trees are a particular implementation of compressed binary trie that utilize binary encoding of the string keys in its representation.[23][15]^: 140 Every node in a Patricia tree contains an index, known as a "skip number", that stores the node's branching index to avoid empty subtrees during traversal.[15]^: 140-141 A naive implementation of a trie consumes immense storage due to larger number of leaf-nodes caused by sparse distribution of keys; Patricia trees can be efficient for such cases.[15]^: 142[24]^: 3

A representation of a Patricia tree with string keys ${\displaystyle \{in,integer,interval,string,structure\}}$ is shown in figure 4, and each index value adjacent to the nodes represents the "skip number" - the index of the bit with which branching is to be decided.[24]^: 3 The skip number 1 at node 0 corresponds to the position 1 in the binary encoded ASCII where the leftmost bit differed in the key set ${\displaystyle X}$.[24]^: 3-4 The skip number is crucial for search, insertion, and deletion of nodes in the Patricia tree, and a bit masking operation is performed during every iteration.[15]^: 143

Lexicographic sorting of a set of string keys can be implemented by building a trie for the given keys and traversing the tree in pre-order fashion;[26] this is also a form of radix sort.[27] Tries are also fundamental data structures for burstsort, which is notable for being the fastest string sorting algorithm as of 2007,[28] accompanied for its efficient use of CPU cache.[29]

A special kind of trie, called a suffix tree, can be used to index all suffixes in a text to carry out fast full-text searches.[30]

A specialized kind of trie called a compressed trie, is used in web search engines for storing the indexes - a collection of all searchable words.[31] Each terminal node is associated with a list of URLs—called occurrence list—to pages that match the keyword. The trie is stored in the main memory, whereas the occurrence is kept in an external storage, frequently in large clusters, or the in-memory index points to documents stored in an external location.[32]

Tries are used in Bioinformatics, notably in sequence alignment software applications such as BLAST, which indexes all the different substring of length k (called k-mers) of a text by storing the positions of their occurrences in a compressed trie sequence databases.[25]^: 75

Compressed variants of tries, such as databases for managing Forwarding Information Base (FIB), are used in storing IP address prefixes within routers and bridges for prefix-based lookup to resolve mask-based operations in IP routing.[25]^: 75