Code-snippets/Trie.h at master · boyxgc/Code-snippets · 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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#ifndef TRIE_H
#define TRIE_H

#include <unordered_map>
#include <string>
using namespace std;

class TrieNode {

public:
    TrieNode() {}
    //TrieNode(char c): value(c) {}

    bool insert(string str) {
        if(str.empty()) {
            if(leaf == true){
                return false;
            }
            else {
                leaf = true;
                return true;
            }
        }

        char first = str[0];
        TrieNode *child;
        if(children.find(first) == children.end()) {
            child = new TrieNode(/*first*/);
            children[first] = child;
        } else {
            child = children[first];
        }

        return child->insert(str.substr(1));
    }

    bool search(string str) {
        if(str.empty()) {
            return leaf;
        }
        char first = str[0];
        if(children.find(first) == children.end()) {
            return false;
        } else {
            return children[first]->search(str.substr(1));
        }
    }

    bool remove(string str) {
        if(str.empty()) {
            leaf = false;
            return true;
        }
        char first = str[0];
        if(children.find(first) == children.end()) {
            return false;
        } else {
            if(!children[first]->remove(str.substr(1))){
                return false;
            }
            else{
                if(children[first]->children.size() == 0 && !children[first]->leaf) {
                    delete children[first];
                    children.erase(first);
                }
                return true;
            }
        }
    }

private:
    //char value;
    bool leaf;
    unordered_map <char, TrieNode *> children;
};

class Trie {

public:
    Trie() {
        root = new TrieNode();
        size = 0;
    }

    bool insert(string str) {
        if(root->insert(str)) {
            size++;
            return true;
        } else {
            fprintf(stderr,"Error inserting duplicate :\"%s\"" " \n", str.c_str());
            return false;
        }

    }

    bool remove(string str) {
        if(root->remove(str) ) {
            size--;
            return true;
        } else {
            fprintf(stderr,"Error remove nonexistence :\"%s\"" " \n", str.c_str());
            return false;
        }
    }

    bool search(string str) {
        return root->search(str);
    }

    int getSize() {
        return size;
    }

private:
    TrieNode *root;
    int size;
};


#endif //TRIE_H