Untitled

mail@pastecode.io avatarunknown
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 */