Trie Data Structure Introduction implementation and application
In this blog post we are going to learn 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