Advertisement
i_love_rao_khushboo

Trie Implementation Using Map

Jul 25th, 2021
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #include<iostream>
  2. #include<unordered_map>
  3. using namespace std;
  4.  
  5. class Node
  6. {
  7.     public:
  8.      char data;
  9.      unordered_map<char, Node*> children;
  10.      bool terminal;
  11.      
  12.      //constructor
  13.      Node(char c)
  14.      {
  15.         data=c;
  16.         terminal=false;
  17.      }
  18. };
  19.  
  20. class Trie
  21. {
  22.     Node *root;
  23.    
  24.     public:
  25.      Trie()
  26.      {
  27.         root=new Node('\0');
  28.      }
  29.      
  30.      void insert(char *w)
  31.      {
  32.         Node *temp=root;
  33.         for(int i=0; w[i]!='\0'; i++)
  34.         {
  35.             char ch=w[i];
  36.             if(temp->children.count(ch))
  37.                 temp=temp->children[ch];
  38.            
  39.             else
  40.             {
  41.                 Node *n=new Node(ch);
  42.                 temp->children[ch]=n;
  43.                 temp=n;
  44.             }
  45.         }
  46.        
  47.         temp->terminal=true;
  48.      }
  49.      
  50.      bool search(char *w)
  51.      {
  52.         Node *temp=root;
  53.         for(int i=0; w[i]!='\0'; i++)
  54.         {
  55.             char ch=w[i];
  56.             if(temp->children.count(ch)==0)
  57.                return false;
  58.                
  59.             else temp=temp->children[ch];
  60.         }
  61.        
  62.         return temp->terminal;
  63.      }
  64. };
  65.  
  66. int main()
  67. {
  68.     char words[][20]={"I", "am", "Iron", "Man", "&", "myself", "GROOT!!"};
  69.     Trie t;
  70.     for(int i=0; i<7; i++)
  71.        t.insert(words[i]);
  72.        
  73.     char w[10];
  74.     cin>>w;
  75.    
  76.     if(t.search(w))
  77.        cout<<"PRESENT in the Trie Data Structure";
  78.        
  79.     else cout<<"ABSENT in the Trie Data Structure";
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement