All the search trees are used to store the collection of numerical values but they are not suitable for storing the collection of words or strings. Trie is a data structure which is used to store the collection of strings and makes searching of a pattern in words more easy. The term trie came from the word retrieval. Trie data structure makes retrieval of a string from the collection of strings more easily. Trie is also called as Prefix Tree and some times Digital Tree. A trie is defined as follows...
Trie is a tree like data structure used to store collection of strings.
A trie can also be defined as follows...
Trie is an efficient information storage and retrieval data structure.
The trie data structure provides fast pattern matching for string data values. Using trie, we bring the search complexity of a string to the optimal limit. A trie searches a string in O(m) time complexity, where m is the length of the string.
In trie, every node except the root stores a character value. Every node in trie can have one or a number of children. All the children of a node are alphabetically ordered. If any two strings have a common prefix then they will have the same ancestors.