Editing Trie (section)

=== 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.