Advanced Data Structure: Trie

i1lrz

Trie is one of the important datastructures used widely in programming. The most important use of Trie is visible in the contact list search operation available in almost all mobile phones today. Trie provides an efficient way to search for a word starting with a prefix.

Many problems in competitive programming are based on trie which provides a very efficient runtime complexity in searching the word. The name trie is derived from the middle letters of retrieve.

Complexity

Using a trie, search operation can be run O(m) ,where m is the length of the string to search. A complete BST(Binary Search Tree) can also be used for the same purpose but it would take O(m*log n) complexity for the search.

Space complexity of a Trie is large. Total size of a trie with N keys is O( alphabets * keyLength * N)

Insert() and Search() are the two operations supported by the Trie. 

This video by Tushar roy is very useful in understanding the concepts of Trie

Code implementation

Each node of the Trie consists of two members 

  1. A mapping for each character to another Trie Node
  2. A boolean value to mark whether the current node is a leaf or not

C /C++

struct TrieNode
{
   struct TrieNode *child[size_of_alphabets];
   bool leaf;

}

Python

class TrieNode:
      def __init__(self):
           self.child=defaultdict(set)
           self.leaf=True

Insertion in Trie

Insertion in Trie is very straightforward. We start with the root node.

void insert(pTrieNode r, char *word)
{
int len=strlen(word);
int index;
int i;

pTrieNode temp=r;

for(int i=0;i<len;i++) { index=find_index(word[i]); if(!temp->children[index])
{
temp->children[index]=newNode();

}

temp=temp->children[index];

}
temp->isLeaf=true;
}

The first character of the key is checked with the root node’s children array to check if the character is present. If not , a new node is created and the slot in children[] array is pointed towards the newNode.

 Complete code for c/c++

#include <bits/stdc++.h>
using namespace std;

typedef struct TrieNode
{
	struct TrieNode* children[26];
	bool isLeaf;
}TrieNode;

typedef TrieNode* pTrieNode;

int find_index(char c)
{
	return ((int)c- int('a'));
}

pTrieNode newNode()
{
	pTrieNode temp=(pTrieNode)malloc(sizeof(TrieNode));

	if(temp)
	{
		for(int i=0;i<26;i++) temp->children[i]=NULL;

		temp->isLeaf=false;
	}

	return temp;

}

bool search(pTrieNode root,  char * word)
{

	pTrieNode temp=root;

	int index;
	int len=strlen(word);
	for(int i=0;i<len;i++) 	{ 		index=find_index(word[i]); 		 		if(!temp->children[index]) { return false;}
		else
		{
			if(temp->isLeaf){ return false;}
			if(i==len-1){ return true;}
			temp=temp->children[index];

		}

	}

}

void insert(pTrieNode r, char *word)
{
	int len=strlen(word);
	int index;
	int i;

	pTrieNode temp=r;

	for(int i=0;i<len;i++) 	{ 		index=find_index(word[i]); 		if(!temp->children[index])
		{
			temp->children[index]=newNode();

		}

		temp=temp->children[index];

	}
	temp->isLeaf=true;
}

int main()
{

	pTrieNode trie=newNode();
	char key[]={"akshay"};
	char searchKey[]={"aks"};
	insert(trie,key);
	cout<<search(trie,searchKey);

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s