Algorithms2021/trie.cpp at main · subh6678/Algorithms2021 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
struct TrieNode
{
	map<char,TrieNode*> mp;
	bool isEnd;
	TrieNode()
	{
		isEnd=false;
	}
};
struct TrieNode* root;

void insertNode(string s)
{
	TrieNode* curr=root;
	for(int i=0;i<s.length();i++)
	{
		if(curr->mp.count(s[i])==0)
		curr->mp[s[i]]=new TrieNode();
		curr=curr->mp[s[i]];
	}
	curr->isEnd=true;
}

void deleteNode(string s)
{
	TrieNode* curr=root, *parent=root;
	char child=s[0];
	for(int i=0;i<s.length();i++)
	{
		if(curr->mp[s[i]]->mp.size()>1)
		{
			parent=curr->mp[s[i]];
			if(i<s.length()-1)
			child=s[i+1];
		}
		curr=curr->mp[s[i]];
	}
	curr->isEnd=false;
	if(curr->mp.empty())
	{
		parent->mp.erase(child);
	}
}

bool searchNode(string s)
{
	TrieNode* curr=root;
	for(int i=0;i<s.length();i++)
	{
		if(curr->mp.count(s[i])==0)
		return false;
		curr=curr->mp[s[i]];
	}
	return curr->isEnd;
}
int main()
{
	root=new TrieNode();
	insertNode("ghanshyam");
	insertNode("ghanshyaminathan");
//	insertNode("qqrs");
//	insertNode("pqst");
//	insertNode("pqrs");
	deleteNode("ghanshyam");
//	deleteNode("pqrs");
	cout<<searchNode("ghanshyaminathan");
	cout<<searchNode("ghanshyam");
}