Trie Data Structure Implementation

Unknown 23:23 , , No comments

Trie can insert and search string in O(L) time where L is the length of string,this is much faster than hashtable and binary search tree implementations. Trie Node consist of a collection of Trie nodes and a boolean flag to check whether node is leaf or not.

Tutorial Links

Tutorial Link

Also Topcoder had excellent explanation about TRIE

Here is the C++ implementation of above Algorithm


/*
  TRIE implementation in C++
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ALPHABET_SIZE 26
using namespace std;
struct Node
{
 struct Node *child[ALPHABET_SIZE];
 bool isLeaf;
};
struct Node *createNode()
{
 Node *nw=new Node;
 for(int i=0;i<26;i++)
  nw->child[i]=NULL;
 nw->isLeaf=0;
 return nw;
}
void addWord(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
  {
   temp->child[c]=createNode();
  }
  temp=temp->child[c];
 }
 temp->isLeaf=1;
}
bool search(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
   return false;
  temp=temp->child[c];
 }
 if(temp->isLeaf)
  return true;
 else
  return false;
}
void printAllStrings(struct Node *root,string s)
{
 if(!root)
  return;
 if(root->isLeaf)
 {
  cout<<s<<"\n";
  return;
 }
 else
 {
  for(int i=0;i<26;i++)
  {
   if(root->child[i])
   {
 
    printAllStrings(root->child[i],s+(char)('a'+i));
   }
  }
 }
}
int main()
{
 struct Node *root=createNode();
 addWord(root,"abcd");
 addWord(root,"ace");
 if(search(root,"sai"))
  cout<<"Sai found\n";
 else
  cout<<"Sai not found\n";
 if(search(root,"abcd"))
  cout<<"abcd found\n";
 else
  cout<<"abcd not found\n";
 printAllStrings(root,"");
}
 

No comments :

Post a Comment

Binary Index Tree

Unknown 10:52 , , No comments

While learning Some advanced data structures I found Binary Index tree,One of the most intresting data Structure and easy to learn if we are familiar with some bit manipulation Techniques.

I found some tutorials on Internet with great Explanation.

Tutorial 1
Tutorial 2

Also Topcoder had excellent explanation about BIT

Here is the C++ implementation of above Algorithm


//C++ implementation of Binary Index Tree
//Array with N elements
//Construction of BIT
//Initialisation
//Updation
//Query Sum of elments in rangle l...r
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[100+1],BIT[100+1],n;
void init()//Initialisation of BIT
{
	for(int i=1;i<=n;i++)
	{
		int val=a[i];
		int idx=i;
		while(idx<=n)
		{
			BIT[idx]+=val;
			idx+=(idx & -idx);
		}
	}
	cout<<"After Initialisation \n";
	for(int i=1;i<=n;i++)
		cout<<BIT[i]<<" ";
	cout<<endl;
}
void update(int pos,int val)//Update the from that Position
{
	int idx=pos;
	while(idx<=n)
	{
		BIT[idx]+=val;
		idx+=(idx & -idx);
	}
	cout<<"After Updation \n";
	for(int i=1;i<=n;i++)
		cout<<BIT[i]<<" ";
	cout<<endl;
}
int query(int idx)
{
	int sum=0;
	while(idx>0)
	{
		sum+=BIT[idx];
		idx-=(idx & -idx);
	}
	return sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	memset(BIT,0,sizeof BIT);
	init();
	int q;
	cin>>q;	
	while(q--)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int x,val;
			cin>>x>>val;
			update(x,val);
		}
		else
		{
			int x,y;
			cin>>x>>y;
 
			cout<<query(y)-query(x-1)<<endl;
		}
 
	}
}

No comments :

Post a Comment

Subscribe to: Posts ( Atom )

Subscribe