of short strings, since nodes share common initial string subsequences and stores the keys implicitly on the structure. The terminal node of the tree contains a non-nil , and it is a search hit if the associated value is found in the trie, and search miss if it isn't. Insertion Insertion into trie is guided by using the character sets as the indexes into the array until last character of the string key is reached. 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. If a link is encountered prior to reaching the last character of the string key, a new is created, such along lines 3–5. gets assigned to input ; if wasn't at the time of insertion, the value associated with the given string key gets substituted with the current one. 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 correspondingly. Following is a recursive procedure for removing a string key () from rooted trie (). The procedures begins by examining the ; 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 ). 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 's index. Replacing other data structures Replacement for hash tables A trie can be used to replace a hash table, over which it has the following advantages: Searching for a node with an associated key of size has the complexity of , whereas an imperfect hash function may have numerous colliding keys, and the worst-case lookup speed of such a table would be , where 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