Untitled
plain_text
a month ago
2.8 kB
0
Indexable
Never
#include<iostream> using namespace std; class trienode{ public: char data; trienode* children[26]; // an array of trienodes bool isterminal; trienode(char ch){ data=ch; for(int i=0;i<26;i++){ children[i]=NULL; } isterminal=false; } }; class trie{ trienode* root; //global in class public: //constructor trie(){ root =new trienode('\0'); //initialises a new trie with root trienode NULL.. this doesnt change } void insertdriver(trienode* root,string str){ if(str.length()==0){ //base case root->isterminal=true; return; } trienode* child; int index=str[0]-'A'; if(root->children[index]!=NULL){ // this character already exists in the children of root .. proceed child=root->children[index]; }else{ child =new trienode(str[0]); // this character isnt present in children of root. create it and then root->children[index]=child; // proceed } insertdriver(child,str.substr(1)); //recursion } void insert(string str){ insertdriver(root,str); } bool searchdriver(trienode* root,string serch){ int index=serch[0]-'A'; if(serch.length()==0) return root->isterminal; //found word if(root->children[index]==NULL) return false; // not found return false return searchdriver(root->children[index],serch.substr(1)); //found this character , proceed to next character } bool search(string serch){ return searchdriver(root,serch); // the root is one only } void removaldriver(trienode* root,string word){ if(word.length()==0 && root->isterminal==true) { root->isterminal=false; return; } int index=word[0]-'A'; removaldriver(root->children[index],word.substr(1)); } void remove(string word){ //assuming word is present, add a check if needed removaldriver(root,word); } }; int main(){ trie* t= new trie(); (*t).insert("ATEEB"); // (*t).insert is same as t->insert t->insert("ISHA"); t->insert("ATE"); cout<<t->search("ATEEB")<<"\n";// 1 cout<<t->search("ISHA")<<"\n"; //1 cout<<t->search("ATE")<<"\n"; //1 t->remove("ISHA"); cout<<t->search("ISHA")<<"\n"; //0 t->remove("ATE"); cout<<t->search("ATEEB")<<"\n"; //1 cout<<t->search("ATE")<<"\n"; //0 return 0; } /* 1trie takes less storage than hashmap because in hashmap all words take unqiue map , but trie shares commonf words in the children array of root 2 trie can also shows suggestions easily */