All the search trees are used to store collection of numerical values but they are not suitable for storing collection of words or strings. Trie is a data structure which is used to store collection of strings and make searching a pattern more easy. The term trie comes from the word retrieval. Trie data structure makes retrieval of a string from a collection of strings more easy. 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 can bring the search complexity of a string to optimal limit. A trie can search a sring in O(m) time where m is the length of the string.
In a trie every node except root stores a character value. Every node in trie can have one or more number of children. All the children of a node are alphabetically ordered. If any two strings have a common prefix then they will have same ancesters.