Trie Data Structure: Introduction, implementation and application
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)
From the above representation it is clear that every vertex represents a word or prefix word but does not represent entire word.
Trie data structure which build a list of words and provides efficient retrieval/query of information. it should provide at least following operation.
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.
Now add “SAD”
Implementation of Trie Data structure and its operation in C++
Application of Trie
- Spell Checking
- Data Compression
- IP Address Routing
- Mobile phone contact list