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.

struct trie
{
   struct trie* children[26];
   int isEndOfString;
}
  • 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.
trie *makeNode() {
	trie *p = malloc(sizeof(trie));

	if (p) {
		p->isEndOfString = false;
		int i = 0;
		for (i; i < 26; i++) {
			p->children[i] = NULL;
		}
	}
	return p;
}
  • 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.
int getIndex(char ch)
{
   return ch - 'a';
}
  • 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
void insert(struct trie * root, char *str, int str_len) {
        struct trie *tmp = root;
        int i = 0;
        for (i; i < str_len; i++) {
                int index_of_char = getIndex(str[i]);
                if (tmp->children[index_of_char] == NULL) {
                        tmp->children[index_of_char] = makeNode();
                }
                tmp = tmp->children[index_of_char];
        }
        // after traversing all char of str,mark
        // last trie node's flag isEndOfString true
        tmp->isEndOfString = true;
}

Search a string in trie

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

#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define true 1
#define false 0

struct trie {
	struct trie *children[26];
	int isEndOfString;
};

struct trie *makeNode() {
	struct trie *p = (struct trie*) malloc(sizeof(struct trie));
	if (p) {
		p->isEndOfString = false;
		int i = 0;
		for (i; i < 26; i++) {
			p->children[i] = NULL;
		}
	}
	return p;
}

int getIndex(char ch) {
	return ch - 'a';
}

void insert(struct trie * root, char *str, int str_len) {
	struct trie *tmp = root;
	int i = 0;
	for (i; i < str_len; i++) {
		int index_of_char = getIndex(str[i]);
		if (tmp->children[index_of_char] == NULL) {
			tmp->children[index_of_char] = makeNode();
		}
		tmp = tmp->children[index_of_char];
	}
	// after traversing all char of str,mark
	// last trie node's flag isEndOfString true
	tmp->isEndOfString = true;
}
int search(struct trie *root, char* str, int len) {

	int i = 0;
	struct trie *tmp = root;

	for (i; i < len; i++) {
		int index = getIndex(str[i]);

		if (!tmp->children[index])
			return false;

		tmp = tmp->children[index];
	}

	return (tmp != NULL && tmp->isEndOfString);
}
int main() {
	// make root Node
	struct trie *root = makeNode();
	char *str = "als";
	int len = strlen(str);
	insert(root, str, len);

	if (search(root, str, len))
		printf("string is present in trie\n");
	else
		printf("string is not present in trie\n");

	char *strr = "wiki";
	if (search(root, strr, len))
		printf("string is present in trie\n");
	else
		printf("string is not present in trie\n");

	return 0;
}

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