Competitive-Programming/Trie.cp at master · potter1024/Competitive-Programming · 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
struct TrieNode{
    map<char,TrieNode*> children;
    bool endofword;
    ll cnt=0;
    TrieNode(){
        endofword=false;
    }
};
TrieNode *root=new TrieNode();
void insert(string word)
{
    TrieNode *current=root;
    for(int i=0;i<word.size();i++)
    {
        char ch=word[i];
        TrieNode *node=current->children[ch];
        if(!node)
        {
            node=new TrieNode();
            current->children[ch]=node;
        }
        current=node;
        current->cnt++;
    }
    current->endofword=true;
}
bool prefixsearch(string word)
{
    TrieNode *current=root;
    for(int i=0;i<word.size();i++)
    {
        char ch=word[i];
        TrieNode *node=current->children[ch];
        if(!node)
            return false;
        current=node;
    }
    return true;
}
bool wordsearch(string word)
{
    TrieNode *current=root;
    for(int i=0;i<word.size();i++)
    {
        char ch=word[i];
        TrieNode *node=current->children[ch];
        if(!node)
            return false;
        current=node;
    }
    if(current->endofword==true)
        return true;
    else
        return false;
}
void delet(TrieNode *node)          // delete the tree
{
    TrieNode *cur=node;
    if(!cur)
    {
        return;
    }
    for(ll i = 0; i <= 25; i++)
    {
        if(cur -> children[(char)(i+'A')])
        {
            delet(cur -> children[(char)(i+'A')]);
        }
    }
    delete(node);
}
void deletion(string word)
{
    TrieNode *current=root;
    for(ll i=0;i<word.size();i++)
    {
        char ch=word[i];
        TrieNode *node=current->children[ch];
        current=node;
        if(i==word.size()-1)
        {
            current->endofword=false;
            break;
        }
    }
}