Editing Trie (section)

== Operations ==
[[File:Trie representation.png|thumb|right|400px|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 nodes that contain links, which either point to other suffix child nodes or ''null''. As for every tree, each node but the root is pointed to by only one other node, called its ''parent''. Each node contains as many links as the number of characters in the applicable [[Alphabet (formal languages)|alphabet]] (although tries tend to have a substantial number of null links). In some cases, the alphabet used is simply that of the [[character encoding]]—resulting in, for example, a size of 256 in the case of (unsigned) [[ASCII]].<ref name="robert11">{{cite book|title=Algorithms|edition=4|first1=Robert|last1=Sedgewick|first2=Kevin|last2=Wayne|author1-link= Robert Sedgewick (computer scientist) |publisher=[[Addison-Wesley]], [[Princeton University]]|date=3 April 2011|isbn= 978-0321573513 |url=https://algs4.cs.princeton.edu/home/}}</ref>{{rp|p=732}}

The null links within the children of a node emphasize the following characteristics:{{r|robert11|p=734}}{{r|brass|p=336}}
# Characters and string keys are implicitly stored in the trie, and include a character [[sentinel value]] indicating string termination.
# Each node contains one possible link to a [[prefix]] of strong keys of the set.

A basic [[Composite data type|structure type]] of nodes in the trie is as follows; <math>\text{Node}</math> may contain an optional <math>\text{Value}</math>, which is associated with each key stored in the last character of string, or terminal node.
{|
|- style="vertical-align:top"
|
 '''structure''' Node
     Children '''Node['''''Alphabet-Size''''']'''
     Is-Terminal '''Boolean'''
     Value '''Data-Type'''
 '''end structure'''
|}

=== Searching ===
Searching for a 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 value for the given string key. A null link during the search indicates the inexistence of the key.{{r| robert11|p=732-733}}

The following pseudocode implements the search procedure for a given string {{mono|key}} in a rooted trie {{mono|x}}.{{r|gonnet91|p=135}}
{|
|- style="vertical-align:top"
|
 Trie-Find(x, key)
     '''for''' 0 &le; 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, {{mono|x}} and {{mono|key}} correspond to the pointer of trie's root node and the string key respectively. The search operation, in a standard trie, takes <math>O(\text{dm})</math> time, where <math>\text{m}</math> is the size of the string parameter <math>\text{key}</math>, and <math>\text{d}</math> corresponds to the [[Alphabet (formal languages)|alphabet size]].<ref name="patil_12">{{cite book|first=Varsha H.|last=Patil|date=10 May 2012|isbn= 9780198066231|publisher=[[Oxford University Press]]|url=https://global.oup.com/academic/product/data-structures-using-c-9780198066231|title=Data Structures using C++}}</ref>{{rp|p=754}} [[Binary search trees]], on the other hand, take <math>O(m \log n)</math> in the worst case, since the search depends on the height of the tree (<math>\log n</math>) of the BST (in case of [[balanced tree]]s), where <math>\text{n}</math> and <math>\text{m}</math> being number of keys and the length of the keys.{{r|reema18|p=358}}

The trie occupies less space in comparison with a BST in the case of a large number of short strings, since nodes share common initial string subsequences and store the keys implicitly.{{r|reema18|p=358}} The terminal node of the tree contains a non-null value, and it is a search ''hit'' if the associated value is found in the trie, and search ''miss'' if it is not.{{r|robert11|p=733}}

=== Insertion ===
Insertion into trie is guided by using the [[Character encoding#Character sets, character maps and code pages|character sets]] as indexes to the children array until the last character of the string key is reached.{{r|robert11|p=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.{{r| gonnet91|p=135}}
{|
|- style="vertical-align:top"
|
 1
 2
 3
 4
 5
 6
 7
 8
 9
|
 Trie-Insert(x, key, value)
     '''for''' 0 &le; 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 null link is encountered prior to reaching the last character of the string key, a new node is created (line 3).{{r|robert11|p=745}} The value of the terminal node is assigned to the input value; therefore, if the former was non-null at the time of insertion, it is substituted with the new value.

=== Deletion ===
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 null correspondingly.{{r|robert11|p=740}}

The following is a [[Recursion (computer science)|recursive]] procedure for removing a string {{mono|key}} from rooted trie ({{mono|x}}).
{|
|- style="vertical-align:top"
| style="text-align: right" |
 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 &le; i &lt; 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 procedure begins by examining the {{mono|key}}; null denotes the arrival of a terminal node or end of a string key. If the node is terminal it has no children, it is removed from the trie (line 14). 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 {{mono|key}}'s index.