The perfect place for easy learning...

Data Structures

×

Topics List

Place your ad here

Tries

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.

Example

trie data structure

Place your ad here
Place your ad here