হ য ব র ল: Trie (Prefix Tree)

Source :

Visualization :

Code :

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

	struct node {
	node* next[27];
	bool endmark;
	node() {
	for(int i = 0; i < 26; i++) {
	next[i] = NULL;
	}
	endmark = false;
	}
	};

	node* root;

	void Insert(string s)
	{
	node* curr = root;
	for(int i = 0; i < s.size(); i++) {
	int id = s[i] - 'a';
	if(curr->next[id]==NULL) {
	curr->next[id] = new node();
	}
	curr = curr->next[id];
	}
	curr->endmark = true;
	}

	bool Search(string s)
	{
	node* curr = root;
	for(int i = 0; i < s.size(); i++) {
	int id = s[i] - 'a';
	if(curr->next[id]==NULL) {
	return false;
	}
	curr = curr->next[id];
	}
	return curr->endmark;
	}

	bool isEmpty(node* curr)
	{
	for(int i = 0; i < 26; i++) {
	if(curr->next[i]) return false;
	}
	return true;
	}

	node* Remove(node* root, string s, int depth = 0)
	{
	if(!root)
	return NULL;
	if(depth==s.size())
	{
	if(root->endmark)
	root->endmark = false;
	if(isEmpty(root))
	{
	delete(root);
	root = NULL;
	}
	return root;
	}
	int index = s[depth] - 'a';
	root->next[index] = Remove(root->next[index], s, depth+1);

	if(isEmpty(root) && root->endmark==false)
	{
	delete(root);
	root = NULL;
	}
	return root;
	}

	void Delete(node* curr)
	{
	for(int i = 0; i < 26; i++) {
	if(curr->next[i]) {
	Delete(curr->next[i]);
	}
	}
	delete(curr);
	}

	int main()
	{
	root = new node();
	int n;
	cin>>n;
	for(int i = 0; i < n; i++) {
	string s;
	cin>>s;
	Insert(s);
	}
	int q;
	cin>>q;
	while(q--) {
	string s;
	cin>>s;
	if(Search(s)) {
	cout<<"Found"<<endl;
	}
	else {
	cout<<"Not Found"<<endl;
	}
	}
	Delete(root); /// RIP Trie...

	return 0;
	}

view raw trie.cpp hosted with ❤ by GitHub

view raw array_trie.cpp hosted with ❤ by GitHub

Applications :

1.Insert, Search, Remove a word from dictionary. [If there are multiple testcases then Delete the trie else it will cause MLE.]

:: Implemented in the given code.

2. Find if a word in dictionary is a prefix of another word from dictionary.

Example : 12345, 1245, 123, 1634... Here 123 is a prefix of 12345.

:: In the time of Insertion we will check if we find a end-mark==true for a word or after ending a word there is a child-node which is not NULL.

3. Find how many time a prefix occurs in a dictionary.

Example : algo, azzy, algea, also, else... Here "al" prefix occurs 3 times.

:: Here we will keep a counter variable in each node. In the time of insertion we will increase it each time.

4. Creating suggestion box. Given a word, print all words whose prefix is this word.

Example : algo, azzy, algea, also, else...Here "al" is given print "algo", "algea", "also".

:: Go to its child node which are not null and print them all.

5. Find maximum & minimum xor of sub-array from an array.

Example : 6 8 2 4 2 have maximum xor = 14 & minimum xor = 2.

:: Read Link2.