In this blog we will learn how to write c program for trie data structure. Trie is one useful data structure which is used in memory constraint system. we have already discussed the basic of trie at http://wikistack.com/trie-data-structure-introduction-implementation-and-application/

In this tutorial we will make trie for alphabets characters only.  It means it only supports string with lower character. we will insert only strings of lower characters. Let us see below figure ,it is a trie.

 

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

So lets us define our data structure.

  • Since we are limiting our implementation to lower alphabets which are 26 , so each node of the trie will contain 26 pointers.

How to insert a string in trie

Let us suppose we need to insert string “als” into the trie.

  • First of all make a root node and initialize all the pointers NULL.

  • Get the index of first character of “als”. in our case it is 0 since index of a would be zero, use below function to get index.

  • Go to the 0th child of the root , check whether it is NULL, if it is null then make a new trie node. This newly created child node is now current node.
  • Now get index of 1st character of string “als”. we will get index 11. since now our index is 11, then go to the 11th index of current trie node, check whether it is NULL or not , if it is NULL , make a new trie node , make it current node. if it is not null make non null trie node as a current node.
  • Now go to the 2nd character , get the index , follow the same procedure as above. So now we can make our insertion function as

Search a string in trie

So far we have implemented our trie with insert operation. Now implement search operation. below is complete c program.

The above program is correct. But there is problem? can you imagine what is problem? it will leak memory. Let us find leak with valgrind memory debugging tool.

How to find memory leak using valgrind memory debugging tool

click here to know how to delete trie data structure completely to prevent memory leak.

Ref:

http://www.ideserve.co.in/learn/trie-insert-and-search




Related Contents to follow