data structures using trie the term trie has been taken from the word 'retrievala trie is an ordered tree data structurewhich was introduced in the by edward fredkin trie stores keys that are usually strings it is basically -ary position tree am do in contrast to binary search treesnodes in trie do not store the keys ar associated with them rathera node' position in the tree represents art dot the key associated with that node all the descendants of node have arm arc are common prefix of the string associated with that nodeand the root is associated with the empty string figure shows trie figure trie data structure in the given treekeys are listed in the nodes and the values below them note that each complete english word is assigned an arbitrary integer value we can find each of these words by traversing the various branches in the tree until leaf node is encountered any path from the root to leaf represents word advantages relative to binary search tree when compared with binary search treethe trie data structure has the following advantages faster search searching for keys is fasteras searching key of length takes (mtime in the worst case on the other handa binary search tree performs (logncomparisons of keyswhere is the number of nodes in the tree since search time depends on the height of the tree which is logarithmic in the number of keys (if the tree is balanced)the worst case may take ( log ntime in addition to thism approaches log(nin the worst case hencea trie data structure provides faster search mechanism less space trie occupies less spaceespecially when it contains large number of short strings since keys are not stored explicitly and nodes are shared between the keys with common initial subsequencesa trie calls for less space as compared to binary search tree longest prefix-matching trie facilitates the longest-prefix matching which enables us to find the key sharing the longest possible prefix of all unique characters since trie provides more advantagesit can be thought of as good replacement for binary search trees advantages relative to hash table trie can also be used to replace hash table as it provides the following advantagessearching for data in trie is faster in the worst caseo(mtimecompared to an imperfect hash tablediscussed in which may have numerous key collisions trie is free from collision of keys problem unlike hash tablethere is no need to choose hash function or to change it when more keys are added to trie trie can sort the keys using predetermined alphabetical ordering disadvantages the disadvantages of having trie are listed belowin some casestries can be slower than hash tables while searching data this is true in cases when the data is directly accessed on hard disk drive or some other secondary storage device that has high random access time as compared to the main memory