Skip to content

Instantly share code, notes, and snippets.

@reterVision

reterVision/trie.cc

Created January 18, 2014 08:39
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save reterVision/8487831 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save reterVision/8487831 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. reterVision created this gist Jan 18, 2014.
    140 changes: 140 additions & 0 deletions trie.cc
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,140 @@
    #include <iostream>
    #include <string>
    #include <map>
    #include <vector>

    using namespace std;

    struct Node {
    char ch;
    map<char, Node*> children;
    };

    class Trie {
    public:
    Trie() { head.ch = -1; };
    ~Trie();

    void build_trie(string words[], int length);
    void insert(string word);
    void search(string word, bool &result);

    void print_tree(map<char, Node*> tree);
    void print();

    protected:
    Node head;
    // Keep all newly created node in an array, for the ease of
    // memory release.
    vector<Node*> children;
    };

    Trie::~Trie() {
    for (int i=0; i<children.size(); ++i) {
    delete children[i];
    }
    }

    void Trie::build_trie(string words[], int length) {
    for (int i=0; i<length; ++i) {
    insert(words[i]);
    }
    }

    void Trie::insert(string word) {
    map<char, Node*> *current_tree = &head.children;
    map<char, Node*>::iterator it;

    for (int i=0; i<word.length(); ++i) {
    char ch = word[i];

    if ((it = current_tree->find(ch)) != current_tree->end()) {
    current_tree = &it->second->children;
    continue;
    }

    if (it == current_tree->end()) {
    // Display inserting position in the tree, for debug use
    //
    // cout << "Inserting " << ch << endl;
    // cout << "on layer " << endl;
    // map<char, Node*>::iterator temp = current_tree->begin();
    // for (; temp != current_tree->end(); ++temp)
    // cout << temp->first << endl;

    Node* new_node = new Node();
    new_node->ch = ch;
    (*current_tree)[ch] = new_node;

    // For continuous inserting a word.
    current_tree = &new_node->children;

    // For the ease of memory clean up.
    children.push_back(new_node);
    }
    }
    }

    void Trie::search(string word, bool &result) {
    map<char, Node*> current_tree = head.children;
    map<char, Node*>::iterator it;

    for (int i=0; i<word.length(); ++i) {
    if ((it = current_tree.find(word[i])) == current_tree.end()) {
    result = false;
    return;
    }
    current_tree = it->second->children;
    }

    result = true;
    return ;
    }

    void Trie::print_tree(map<char, Node*> tree) {
    if (tree.empty()) {
    return;
    }

    for (map<char, Node*>::iterator it=tree.begin(); it!=tree.end(); ++it) {
    cout << it->first << endl;
    print_tree(it->second->children);
    }
    }

    void Trie::print() {
    map<char, Node*> current_tree = head.children;
    print_tree(current_tree);
    }


    int main(int argc, char** argv)
    {
    string words[] = {"foo", "bar", "baz", "barz"};
    Trie trie;
    trie.build_trie(words, 4);
    cout << "All nodes..." << endl;
    trie.print();

    cout << "Searching..." << endl;
    bool in_trie = false;
    trie.search("foo", in_trie);
    cout << "foo " << in_trie << endl;

    trie.search("fooz", in_trie);
    cout << "fooz " << in_trie << endl;

    trie.search("bar", in_trie);
    cout << "bar " << in_trie << endl;

    trie.search("baz", in_trie);
    cout << "baz " << in_trie << endl;

    trie.search("barz", in_trie);
    cout << "barz " << in_trie << endl;;

    trie.search("bbb", in_trie);
    cout << "bbb " << in_trie << endl;;

    return 0;
    }