What is it?

We are assuming that readers of this article is familiar with tree data structure. A Trie is a special type of tree where each vertex represents a word or prefix while its root contains empty string (“”).

  • root of the tree contains empty string (” “).
  • Any vertex may represents a word prefix.
  • The length of child node/vertex is equal to the distance from the root.

Let Us look at the below Trie for A trie for keys “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn” (source Wikipedia)

250px-Trie_example.svg

From the above representation it is clear that every vertex represents a word or prefix word but does not represent entire word.

Operation support

Trie data structure which build a list of words and provides efficient retrieval/query of information. it should provide at least following operation.

  • search
  • insert
  • remove

Before implementing Trie let us see How Trie works

We know that root of trie contains a null string. Now suppose we need to insert  “SAY” in trie. So we have to build a tree of node where each node represents character. The last node is NULL,which shows end of the string.

trieNow add “NO”

trie1

Now add “SAD”

trie2

Implementation of Trie Data structure and its operation in C++

 

Application of Trie

  • Spell Checking
  • Data Compression
  • IP Address Routing
  • Mobile phone contact list