Editing Trie (section)

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