Trie

K-ary search tree data structure

This article is about a tree data structure. For the French commune, see Trie-sur-Baïse.

Trie

Type| tree
Invented| 1960
Invented by| Edward Fredkin, Axel Thue, and René de la Briandais
Time complexity in big O notation
| Algorithm|  Average|  Worst case

|
|

Space|  O(n)|  O(n)
Search|  O(n)|  O(n)
Insert|  O(n)|  O(n)
Delete|  O(n)|  O(n)

File:Trie example.svg

Fig. 1: A trie for keys "A", "to", "tea", "ted", "ten", "i", "in", and "inn". Each complete English word has an arbitrary integer value associated with it.

In computer science, a trie, also called digital tree or prefix tree,[1] is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key.

Unlike a binary search tree, nodes in the trie do not store their associated key. Instead, a node's position in the trie defines the key with which it is associated. This distributes the value of each key across the data structure, and means that not every node necessarily has an associated value.

All the children of a node have a common prefix of the string associated with that parent node, and the root is associated with the empty string. This task of storing data accessible by its prefix can be accomplished in a memory-optimized way by employing a radix tree.

Though tries can be keyed by character strings, they need not be. The same algorithms can be adapted for ordered lists of any underlying type, e.g. permutations of digits or shapes. In particular, a bitwise trie is keyed on the individual bits making up a piece of fixed-length binary data, such as an integer or memory address. The key lookup complexity of a trie remains proportional to the key size. Specialized trie implementations such as compressed tries are used to deal with the enormous space requirement of a trie in naive implementations.

## Contents

* 1 History, etymology, and pronunciation
* 2 Overview
* 3 Operations
* 3.1 Searching
* 3.2 Insertion
* 3.3 Deletion
* 4 Replacing other data structures
* 4.1 Replacement for hash tables
* 5 Implementation strategies
* 5.1 Bitwise tries
* 5.2 Compressed tries
* 5.2.1 Patricia trees
* 6 Applications
* 6.1 Sorting
* 6.2 Full-text search
* 6.3 Web search engines
* 6.4 Bioinformatics
* 6.5 Internet routing
* 7 See also
* 8 References
* 9 External links

## History, etymology, and pronunciation[edit | edit source]

The idea of a trie for representing a set of strings was first abstractly described by Axel Thue in 1912.[2][3] Tries were first described in a computer context by René de la Briandais in 1959.[4][3][5]: 336

The idea was independently described in 1960 by Edward Fredkin,[6] who coined the term trie, pronouncing it /ˈtriː/ (as "tree"), after the middle syllable of retrieval.[7][8] However, other authors pronounce it /ˈtraɪ/ (as "try"), in an attempt to distinguish it verbally from "tree".[7][8][3]

## Overview[edit | edit source]

Tries are a form of string-indexed look-up data structure, which is used to store a dictionary list of words that can be searched on in a manner that allows for efficient generation of completion lists.[9][10]: 1 A prefix trie is an ordered tree data structure used in the representation of a set of strings over a finite alphabet set, which allows efficient storage of words with common prefixes.[1]

Tries can be efficacious on string-searching algorithms such as predictive text, approximate string matching, and spell checking in comparison to a binary search trees.[11][8][12]: 358 A trie can be seen as a tree-shaped deterministic finite automaton.[13]

## Operations[edit | edit source]

File:Trie representation.png

Fig. 2: Trie representation of the string sets: sea, sells, and she.

Tries support various operations: insertion, deletion, and lookup of a string key. Tries are composed of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{nodes}} that contain links that are either references to other child suffix child nodes, or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{nil}} . Except for root, each node is pointed to by just one other node, called the parent. Each node contains Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{R}} links, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{R}} is the cardinality of the set of alphabets, although tries have a substantial number of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{nil}} links. In most cases, the size of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Children}} array is bitlength of the character encoding \- 256 in the case of (unsigned) ASCII.[14]: 732

The Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{nil}} links within Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Children}} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Node}} emphasizes the following characteristics:[14]: 734 [5]: 336

1. Characters and string keys are implicitly stored in the trie data structure representation, and include a character sentinel value indicating string-termination.
2. Each node contains one possible link to a prefix of strong keys of the set.

A basic structure type of nodes in the trie is as follows; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Node}} may contain an optional Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Value}} , which is associated with each key stored in the last character of string, or terminal node.

structure Node
Children Node[Alphabet-Size]
Is-Terminal Boolean
Value Data-Type
end structure

### Searching[edit | edit source]

Searching a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Value}} for the given string key. A Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{key}} ) in a rooted trie (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{x}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\text{dm})} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{m}} is the size of the string parameter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{key}} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{d}} corresponds to the alphabet size.[16]: 754 Binary search trees, on the other hand, take Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(m \log n)} on the worst case, since the search depends on the height of the tree (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log n} ) of the BST (in case of balanced trees), where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{n}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Value}} , and it is a search hit if the associated value is found in the trie, and search miss if it isn't.[14]: 733

### Insertion[edit | edit source]

Insertion into trie is guided by using the character sets as the indexes into the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 patten of the top-down radix sort.[15]: 135

1    Trie-Insert(x, key, value)
2      for 0 ≤ i < key.length do
3        if x.Children[key[i]] = nil then
4          x.Children[key[i]] := Node()
5        end if
6        x := x.Children[key[i]]
7      repeat
8      x.Value := value
9      x.Is-Terminal := True

If a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{nil}} link is encountered prior to reaching the last character of the string key, a new Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Node}} is created, such along lines 3-5.[14]: 745 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{x.Value}} gets assigned to input Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{value}} ; if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{x.Value}} wasn't Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{nil}} at the time of insertion, the value associated with the given string key gets substituted with the current one.

### Deletion[edit | edit source]

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{nil}} correspondingly.[14]: 740

Following is a recursive procedure for removing a string key (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{key}} ) from rooted trie (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{x}} ).

1    Trie-Delete(x, key)
2      if key = nil then
3        if x.Is-Terminal = True then
4          x.Is-Terminal := False
5          x.Value := nil
6        end if
7        for 0 &le i &lg x.Children.length
8          if x.Children[i] != nil
9            return x
10         end if
11       repeat
12        return nil
13      end if
14      x.Children[key[0]] := Trie-Delete(x.Children[key[0]], key[1:])
15     return x

The procedures begins by examining the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{key}} ; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{key}} 's index.

## Replacing other data structures[edit | edit source]

### Replacement for hash tables[edit | edit source]

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} has the complexity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(N)} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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]

## Implementation strategies[edit | edit source]

File:Pointer implementation of a trie.svg

Fig. 3: A trie implemented as a left-child right-sibling binary tree: vertical arrows are child pointers, dashed horizontal arrows are next pointers. The set of strings stored in this trie is {baby, bad, bank, box, dad, dance}. The lists are sorted to allow traversal in lexicographic order.

Tries can be represented in several ways, corresponding to different trade-offs between memory use and speed of the operations.[5]: 341 Using a vector of pointers for representing a trie consumes enormous space; however, memory space can be reduced at the expense of running time if a singly linked list is used for each node vector, as most entries of the vector contains Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{nil}} .[3]: 495

Techniques such as alphabet reduction may alleviate the high space complexity by reinterpreting the original string as a long string over a smaller alphabet i.e. a string of n bytes can alternatively be regarded as a string of 2n four-bit units and stored in a trie with sixteen pointers per node. However, lookups need to visit twice as many nodes in the worst-case, although space requirements go down by a factor of eight.[5]: 347–352 Other techniques include storing a vector of 256 ASCII pointers as a bitmap of 256 bits representing ASCII alphabet, which reduces the size of individual nodes dramatically.[18]

### Bitwise tries[edit | edit source]

See also: x-fast trie and Bitwise trie with bitmap

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]

### Compressed tries[edit | edit source]

Main article: Radix tree

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 under the following conditions where 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]

#### Patricia trees[edit | edit source]

File:Patricia tree.png

File:Patricia tree ASCII to binary.png

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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

## Applications[edit | edit source]

Trie data structures are commonly used in predictive text or autocomplete dictionaries, and approximate matching algorithms.[11] Tries enable faster searches, occupy less space, especially when the set contains large number of short strings, thus used in spell checking, hyphenation applications and longest prefix match algorithms.[8][12]: 358 However, if storing dictionary words is all that is required (i.e. there is no need to store metadata associated with each word), a minimal deterministic acyclic finite state automaton (DAFSA) or radix tree would use less storage space than a trie. This is because DAFSAs and radix trees can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored. String dictionaries are also utilized in natural language processing, such as finding lexicon of a text corpus.[25]: 73

### Sorting[edit | edit source]

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]

### Full-text search[edit | edit source]

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]

### Web search engines[edit | edit source]

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]

### Bioinformatics[edit | edit source]

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

### Internet routing[edit | edit source]

See also: Luleå algorithm

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

## See also[edit | edit source]

* Suffix tree
* Hash trie
* Hash array mapped trie
* Prefix hash tree
* Ctrie
* HAT-trie

## References[edit | edit source]

1. ^ a b Maabar, Maha (17 November 2014). "Trie Data Structure". CVR, University of Glasgow. Archived from the original on 27 January 2021. Retrieved 17 April 2022.
2. ^ Thue, Axel (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen". Skrifter Udgivne Af Videnskabs-Selskabet I Christiania. 1912 (1): 1–67. Cited by Knuth.
3. ^ a b c d Knuth, Donald (1997). "6.3: Digital Searching". The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 492\. ISBN 0-201-89685-0.
4. ^ de la Briandais, René (1959). File searching using variable length keys (PDF). Proc. Western J. Computer Conf. pp. 295–298. doi:10.1145/1457838.1457895. S2CID 10963780. Archived from the original (PDF) on 2020-02-11. Cited by Brass and by Knuth.
5. ^ a b c d Brass, Peter (8 September 2008). Advanced Data Structures. UK: Cambridge University Press. doi:10.1017/CBO9780511800191. ISBN 978-0521880374.
6. ^ a b Edward Fredkin (1960). "Trie Memory". Communications of the ACM. 3 (9): 490–499. doi:10.1145/367390.367400. S2CID 15384533.
7. ^ a b Black, Paul E. (2009-11-16). "trie". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Archived from the original on 2011-04-29.
8. ^ a b c d e Franklin Mark Liang (1983). Word Hy-phen-a-tion By Com-put-er (PDF) (Doctor of Philosophy thesis). Stanford University. Archived (PDF) from the original on 2005-11-11. Retrieved 2010-03-28.
9. ^ "Trie". School of Arts and Science, Rutgers University. 2022. Archived from the original on 17 April 2022. Retrieved 17 April 2022.
10. ^ Connelly, Richard H.; Morris, F. Lockwood (1993). "A Generalization of the Trie Data Structure". Electrical Engineering and Computer Science. New York: Syracuse University. doi:10.1017/S0960129500000803.
11. ^ a b Aho, Alfred V.; Corasick, Margaret J. (Jun 1975). "Efficient String Matching: An Aid to Bibliographic Search" (PDF). Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855. S2CID 207735784.
12. ^ a b c d e f Thareja, Reema (13 October 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.
13. ^ Daciuk, Jan (24 June 2003). Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings. International Conference on Implementation and Application of Automata. Springer Publishing. pp. 255–261. doi:10.1007/3-540-44977-9_26. ISBN 978-3-540-40391-3.
14. ^ a b c d e f g Sedgewick, Robert; Wayne, Kevin (3 April 2011). Algorithms (4 ed.). Addison-Wesley, Princeton University. ISBN 978-0321573513.
15. ^ a b c d e f Gonnet, G. H.; Yates, R. Baeza (January 1991). Handbook of algorithms and data structures: in Pascal and C (2 ed.). Boston, United States: Addison-Wesley. ISBN 978-0-201-41607-7.
16. ^ Patil, Virsha H. (10 May 2012). Data Structures using C++. Oxford University Press. ISBN 9780198066231.
17. ^ S. Orley; J. Mathews. "The IEEE 754 Format". Department of Mathematics and Computer Science, Emory University. Archived from the original on 28 March 2022. Retrieved 17 April 2022.
18. ^ Bellekens, Xavier (2014). "A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems". Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14. Glasgow, Scotland, UK: ACM. pp. 302:302–302:309. arXiv:1704.02272. doi:10.1145/2659651.2659723. ISBN 978-1-4503-3033-6. S2CID 12943246.
19. ^ a b Willar, Dan E. (27 January 1983). "Log-logarithmic worst-case range queries are possible in space O(n)". Information Processing Letters. ScienceDirect. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3.
20. ^ Sartaj Sahni (2004). "Data Structures, Algorithms, & Applications in C++: Tries". University of Florida. Archived from the original on 16 July 2016. Retrieved 17 April 2022.
21. ^ Mehta, Dinesh P.; Sahni, Sartaj (7 March 2018). "Tries". Handbook of Data Structures and Applications (2 ed.). Chapman & Hall, University of Florida. ISBN 978-1498701853.
22. ^ Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard E. Watson (1 March 2000). "Incremental Construction of Minimal Acyclic Finite-State Automata". Computational Linguistics. MIT Press. 26 (1): 3–16. arXiv:cs/0007009. Bibcode:2000cs........7009D. doi:10.1162/089120100561601.
23. ^ "Patricia tree". National Institute of Standards and Technology. Archived from the original on 14 February 2022. Retrieved 17 April 2022.
24. ^ a b c Crochemore, Maxime; Lecroq, Thierry (2009). "Trie". Encyclopedia of Database Systems. Boston, United States: Springer Publishing. doi:10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0 - via HAL (open archive).
25. ^ a b c Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (March 2016). "Practical compressed string dictionaries". Information Systems. Elsevier. 56: 73–108. doi:10.1016/j.is.2015.08.008. ISSN 0306-4379.
26. ^ Kärkkäinen, Juha. "Lecture 2" (PDF). University of Helsinki. "The preorder of the nodes in a trie is the same as the lexicographical order of the strings they represent assuming the children of a node are ordered by the edge labels."
27. ^ Kallis, Rafael (2018). "The Adaptive Radix Tree (Report #14-708-887)" (PDF). University of Zurich: Department of Informatics, Research Publications.
28. ^ Ranjan Sinha and Justin Zobel and David Ring (Feb 2006). "Cache-Efficient String Sorting Using Copying" (PDF). ACM Journal of Experimental Algorithmics. 11: 1–32. doi:10.1145/1187436.1187439. S2CID 3184411.
29. ^ J. Kärkkäinen and T. Rantala (2008). "Engineering Radix Sort for Strings". In A. Amir and A. Turpin and A. Moffat (ed.). String Processing and Information Retrieval, Proc. SPIRE. Lecture Notes in Computer Science. Vol. 5280\. Springer. pp. 3–14. doi:10.1007/978-3-540-89097-3_3. ISBN 978-3-540-89096-6.
30. ^ Giancarlo, Raffaele (28 May 1992). "A Generalization of the Suffix Tree to Square Matrices, with Applications". SIAM Journal on Computing. Society for Industrial and Applied Mathematics. 24 (3): 520–562. doi:10.1137/S0097539792231982. ISSN 0097-5397.
31. ^ Yang, Lai; Xu, Lida; Shi, Zhongzhi (23 March 2012). "An enhanced dynamic hash TRIE algorithm for lexicon search". Enterprise Information Systems. 6 (4): 419–432. doi:10.1080/17517575.2012.665483.
32. ^ Transier, Frederik; Sanders, Peter (December 2010). "Engineering basic algorithms of an in-memory text search engine". ACM Transactions on Information Systems. Association for Computing Machinery. 29 (1): 1–37. doi:10.1145/1877766.1877768.

## External links[edit | edit source]

Wikimedia Commons has media related to Trie.

File:Wiktionary-logo-en-v2.svg

Look up trie in Wiktionary, the free dictionary.

* NIST's Dictionary of Algorithms and Data Structures: Trie

* v
* t
* e

Tree data structures

Search trees
(dynamic sets/associative arrays)|

* 2–3
* 2–3–4
* AA
* (a,b)
* AVL
* B
* B+
* B*
* Bx
* (Optimal) Binary search
* Dancing
* HTree
* Interval
* Order statistic
* (Left-leaning) Red–black
* Scapegoat
* Splay
* T
* Treap
* UB
* Weight-balanced

Heaps|

* Binary
* Binomial
* Brodal
* Fibonacci
* Leftist
* Pairing
* Skew
* van Emde Boas
* Weak

Tries|

* Ctrie
* C-trie (compressed ADT)
* Hash
* Radix
* Suffix
* Ternary search
* X-fast
* Y-fast

Spatial data partitioning trees|

* Ball
* BK
* BSP
* Cartesian
* Hilbert R
* k-d (implicit k-d)
* M
* Metric
* MVP
* Octree
* PH
* Priority R
* Quad
* R
* R+
* R*
* Segment
* VP
* X

Other trees|

* Cover
* Exponential
* Fenwick
* Finger
* Fractal tree index
* Fusion
* Hash calendar
* iDistance
* K-ary
* Left-child right-sibling
* Link/cut
* Log-structured merge
* Merkle
* PQ
* Range
* SPQR
* Top

* v
* t
* e

Well-known data structures

Types|

* Collection
* Container

Abstract|

* Associative array
* Multimap
* Retrieval Data Structure
* List
* Stack
* Queue
* Double-ended queue
* Priority queue
* Double-ended priority queue
* Set
* Multiset
* Disjoint-set

Arrays|

* Bit array
* Circular buffer
* Dynamic array
* Hash table
* Hashed array tree
* Sparse matrix

Linked|

* Association list
* Linked list
* Skip list
* Unrolled linked list
* XOR linked list

Trees|

* B-tree
* Binary search tree
* AA tree
* AVL tree
* Red–black tree
* Self-balancing tree
* Splay tree
* Heap
* Binary heap
* Binomial heap
* Fibonacci heap
* R-tree
* R* tree
* R+ tree
* Hilbert R-tree
* Trie
* Hash tree

Graphs|

* Binary decision diagram
* Directed acyclic graph
* Directed acyclic word graph

* List of data structures

* v
* t
* e

Strings

String metric|

* Approximate string matching
* Bitap algorithm
* Damerau–Levenshtein distance
* Edit distance
* Gestalt Pattern Matching
* Hamming distance
* Jaro–Winkler distance
* Lee distance
* Levenshtein automaton
* Levenshtein distance
* Wagner–Fischer algorithm

String-searching algorithm|

* Apostolico–Giancarlo algorithm
* Boyer–Moore string-search algorithm
* Boyer–Moore–Horspool algorithm
* Knuth–Morris–Pratt algorithm
* Rabin–Karp algorithm

Multiple string searching|

* Aho–Corasick
* Commentz-Walter algorithm

Regular expression|

* Comparison of regular-expression engines
* Regular grammar
* Thompson's construction
* Nondeterministic finite automaton

Sequence alignment|

* Hirschberg's algorithm
* Needleman–Wunsch algorithm
* Smith–Waterman algorithm

Data structure|

* DAFSA
* Suffix array
* Suffix automaton
* Suffix tree
* Generalized suffix tree
* Rope
* Ternary search tree
* Trie

Other|

* Parsing
* Pattern matching
* Compressed pattern matching
* Longest common subsequence
* Longest common substring
* Sequential pattern mining
* Sorting

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template