C++ implementation of dictionary tree (prefix tree)Tries

lexicographic search trees: tries

// My dictionary tree is based on the longest word in leetcode 720
#include<cstring>
template<int Maxnum_children>
class Index
{
public:
    int operator[] (const char vchar)
    {
        returnvchar % Maxnum_children; }};template<int Maxnum_children>
struct Trie_node
{
    int num_children; // The number of children
    int freq; // Repeat the word frequency
    Trie_node* children[Maxnum_children]; // A pointer to a child node
    Trie_node() : freq(0), num_children(0)
    {
        //for (int i = 0; i < Maxnum_children; ++i) children[i] = NULL;
        memset(children, 0.sizeof(children));
    }
    ~Trie_node()
    {
        for (int i = 0; i < Maxnum_children; ++i)
        {
            delete children[i];
            children[i] = NULL; // delete after NULL?? Compare these two lines}}};template<int Maxnum_children, class Alphabetic_order>
class Trie {
public: // Add method prototypes here.
    typedef Trie_node<Maxnum_children> Node;
    typedef Trie_node<Maxnum_children>* pNode;

    //Trie() :root(new Trie_node<Maxnum_children>()),index(Alphabetic_order()) {}
    Trie() :root(new Trie_node<Maxnum_children>()) {}

    pNode get_root(a) const
    {
        return root;
    }

    template <typename Iterator>
    void insert(Iterator beg, Iterator end);
    void insert(const char* new_entry);

    template <typename Iterator>
    int get_freq(Iterator beg, Iterator end); // Cannot be const??
    int get_freq(const char* target);

    template <typename Iterator>
    bool find(Iterator beg, Iterator end);
    bool find(const char* target);

    template <typename Iterator>
    bool erase(Iterator beg, Iterator end);
    bool erase(const char* target);
    template <typename Iterator>
    bool erase_node(Iterator begin, Iterator end, pNode to_delete);


private: // data members
    pNode root;
    Alphabetic_order index; // the letter corresponds to the subscript value of the child node
};

template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
void Trie<Maxnum_children, Alphabetic_order>::insert(Iterator beg, Iterator end)
{
    pNode current = root;
    while(beg ! = end) {if(! current->children[index[*beg]])// If there is no child node for the current character
        {
            current->children[index[*beg]] = new Node;
            ++current->num_children; // The number of current child nodes increases by 1
            A ++ is from left to right, priority 2 ++ is from right to left, priority 3 is --current->freq and current->freq-- same as (current->freq) */
        }
        current = current->children[index[*beg]];
        beg++;
    }
    ++current->freq;
}

/* Insert string, an overloaded version of c-style string */
template<int Maxnum_children, class Alphabetic_order>
void Trie<Maxnum_children, Alphabetic_order>::insert(const char* new_entry)
{
    return insert(new_entry, new_entry + strlen(new_entry));
}


template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
int Trie<Maxnum_children, Alphabetic_order>::get_freq(Iterator beg, Iterator end)// const: cannot be a const function, or we will fail to match the argument list "(const Alphabetic_order, const char)"
{
    pNode current = root;
    while(beg ! = end) {if(! current->children[index[*beg]])// If there is no child node for the current character
        {
            cerr << "No such string to get frequency.\n";
            return 0; // return false for find()
        }
        current = current->children[index[*beg]];
        beg++;
    }
    return current->freq; // Cannot return true directly because there may be nodes that are just passing by
}

template<int Maxnum_children, class Alphabetic_order>
int Trie<Maxnum_children, Alphabetic_order>::get_freq(const char* target)
{
    return get_freq(target, target + strlen(target));
}


template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
bool Trie<Maxnum_children, Alphabetic_order>::find(Iterator beg, Iterator end)
{
    return get_freq(beg,end) > 0; 
}

template<int Maxnum_children, class Alphabetic_order>
bool Trie<Maxnum_children, Alphabetic_order>::find(const char* target)
{
    return find(target, target + strlen(target));
}

template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
bool Trie<Maxnum_children, Alphabetic_order>::erase(Iterator beg, Iterator end)
{
    return erase_node(beg, end, root);
}

template<int Maxnum_children, class Alphabetic_order>
bool Trie<Maxnum_children, Alphabetic_order>::erase(const char* target)
{
    return erase(target, target + strlen(target));
}

template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
bool Trie<Maxnum_children, Alphabetic_order>::erase_node(Iterator beg, Iterator end, pNode to_delete)
{
    if (beg == end) // When the end of the string is reached, the recursion terminates
    {
        if (to_delete->freq > 0)
        {
            --to_delete->freq; // the word frequency is reduced by one
            return to_delete->freq == 0 && to_delete->num_children == 0; // Delete only if there are no child nodes
        }
        else
        {
            cerr << "No such node to erase.\n";
            return false; }}if(! to_delete->children[index[*beg]]) {cerr << "No such node to erase.\n";
        return false;
    }
    // Determine whether to delete the passing node that did not reach the end of the string
    else if (erase_node((++beg)--, end, to_delete->children[index[*beg]]))
        // Delete In addition to whether to delete the destination node, we also need to consider whether the last segment of the path with freq 0 can be deleted
    {
        delete to_delete->children[index[*beg]];
        --to_delete->num_children;
        // If the current node is a leaf, notify its parent to delete it
        return to_delete->freq == 0 && to_delete->num_children == 0;
    }
    return false;
}

Copy the code

int main(a)
{  
    const int maxnum_children = 26;
    Trie_node<maxnum_children>* trie_node = new Trie_node<maxnum_children>();
    Index<maxnum_children> idx;
    cout << 'a' % maxnum_children << ","<<idx['a'] < <endl;
    cout << 'b' % maxnum_children << "," << idx['b'] < <endl;
    cout << 'B' % maxnum_children << "," << idx['B'] < <endl;
    Trie<maxnum_children, Index<maxnum_children>> trie;
    trie.get_root();
    trie.insert("free");
    trie.insert("tree");
    trie.insert("tree");
    trie.erase("tree");
    trie.erase("tea");
    trie.insert("tea");
    if (trie.find("tea"))cout << "True\n";
    else cout << "False\n";
    trie.insert("team");
    trie.insert("teammate");
    trie.insert("teammate");
    trie.insert("teamwork");
    cout << trie.get_freq("teammate") < <endl;
    
    
    return 0;
}
Copy the code

About const functions

// leetcode 208
const int Maxnum_children=26;
class Index
{
public:
    int operator[] (const char vchar) const // We can add const to Trie search
    {
        returnvchar % Maxnum_children; }};struct Trie_node
{
    int num_children; // The number of children
    int freq; // Repeat the word frequency
    Trie_node* children[Maxnum_children]; // A pointer to a child node
    Trie_node() : freq(0), num_children(0)
    {
        memset(children, 0.sizeof(children));
    }
    ~Trie_node()
    {
        for (int i = 0; i < Maxnum_children; ++i)
        {
            delete children[i];
            children[i] = NULL; }}};class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root=new Trie_node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        auto beg=word.begin();
        auto end=word.end();
        auto current=root;
        while(beg! =end) {if(! current->children[index[*beg]]) { current->children[index[*beg]]=new Trie_node();
                ++current->num_children;
            }
            current = current->children[index[*beg]];
            beg++;
        }
        ++current->freq;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) const{
        auto beg=word.begin();
        auto end=word.end();
        auto current=root;
        while(beg! =end) {if(! current->children[index[*beg]]) {return false;
            }
            current = current->children[index[*beg]];
            beg++;
        }
        return current->freq>0;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        auto beg=prefix.begin();
        auto end=prefix.end();
        auto current=root;
        while(beg! =end) {if(! current->children[index[*beg]]) {return false;
            }
            current = current->children[index[*beg]];
            beg++;
        }
        return true;
    }
private:
    Trie_node* root;
    Index index;
};

/** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); * /
Copy the code

Set the Index [] overload to const, so that the find and get_freq functions in Trie can be const

#include<cstring>
template<int Maxnum_children>
class Index
{
public:
    int operator[] (const char vchar) const
    {
        returnvchar % Maxnum_children; }};template<int Maxnum_children>
struct Trie_node
{
    int num_children; // The number of children
    int freq; // Repeat the word frequency
    Trie_node* children[Maxnum_children]; // A pointer to a child node
    Trie_node() : freq(0), num_children(0)
    {
        //for (int i = 0; i < Maxnum_children; ++i) children[i] = NULL;
        memset(children, 0.sizeof(children));
    }
    ~Trie_node()
    {
        for (int i = 0; i < Maxnum_children; ++i)
        {
            delete children[i];
            children[i] = NULL; // delete after NULL?? Compare these two lines}}};template<int Maxnum_children, class Alphabetic_order>
class Trie {
public: // Add method prototypes here.
    typedef Trie_node<Maxnum_children> Node;
    typedef Trie_node<Maxnum_children>* pNode;

    //Trie() :root(new Trie_node<Maxnum_children>()),index(Alphabetic_order()) {}
    Trie() :root(new Trie_node<Maxnum_children>()) {}

    pNode get_root(a) const
    {
        return root;
    }

    template <typename Iterator>
    void insert(Iterator beg, Iterator end);
    void insert(const char* new_entry);

    template <typename Iterator>
    int get_freq(Iterator beg, Iterator end) const;
    int get_freq(const char* target) const;

    template <typename Iterator>
    bool find(Iterator beg, Iterator end) const;
    bool find(const char* target) const;

    template <typename Iterator>
    bool erase(Iterator beg, Iterator end);
    bool erase(const char* target);
    template <typename Iterator>
    bool erase_node(Iterator begin, Iterator end, pNode to_delete);


private: // data members
    pNode root;
    Alphabetic_order index; // the letter corresponds to the subscript value of the child node
};

template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
void Trie<Maxnum_children, Alphabetic_order>::insert(Iterator beg, Iterator end)
{
    pNode current = root;
    while(beg ! = end) {if(! current->children[index[*beg]])// If there is no child node for the current character
        {
            current->children[index[*beg]] = new Node;
            ++current->num_children; // The number of current child nodes increases by 1
            A ++ is from left to right, priority 2 ++ is from right to left, priority 3 is --current->freq and current->freq-- same as (current->freq) */
        }
        current = current->children[index[*beg]];
        beg++;
    }
    ++current->freq;
}

/* Insert string, an overloaded version of c-style string */
template<int Maxnum_children, class Alphabetic_order>
void Trie<Maxnum_children, Alphabetic_order>::insert(const char* new_entry)
{
    return insert(new_entry, new_entry + strlen(new_entry));
}


template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
int Trie<Maxnum_children, Alphabetic_order>::get_freq(Iterator beg, Iterator end) const
{
    pNode current = root;
    while(beg ! = end) {if(! current->children[index[*beg]])// If there is no child node for the current character
        {
            cerr << "No such string to get frequency.\n";
            return 0; // return false for find()
        }
        current = current->children[index[*beg]];
        beg++;
    }
    return current->freq; // Cannot return true directly because there may be nodes that are just passing by
}

template<int Maxnum_children, class Alphabetic_order>
int Trie<Maxnum_children, Alphabetic_order>::get_freq(const char* target) const
{
    return get_freq(target, target + strlen(target));
}


template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
bool Trie<Maxnum_children, Alphabetic_order>::find(Iterator beg, Iterator end) const
{
    return get_freq(beg,end) > 0; 
}

template<int Maxnum_children, class Alphabetic_order>
bool Trie<Maxnum_children, Alphabetic_order>::find(const char* target) const
{
    return find(target, target + strlen(target));
}

template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
bool Trie<Maxnum_children, Alphabetic_order>::erase(Iterator beg, Iterator end)
{
    return erase_node(beg, end, root);
}

template<int Maxnum_children, class Alphabetic_order>
bool Trie<Maxnum_children, Alphabetic_order>::erase(const char* target)
{
    return erase(target, target + strlen(target));
}

template<int Maxnum_children, class Alphabetic_order>
template <typename Iterator>
bool Trie<Maxnum_children, Alphabetic_order>::erase_node(Iterator beg, Iterator end, pNode to_delete)
{
    if (beg == end) // When the end of the string is reached, the recursion terminates
    {
        if (to_delete->freq > 0)
        {
            --to_delete->freq; // the word frequency is reduced by one
            return to_delete->freq == 0 && to_delete->num_children == 0; // Delete only if there are no child nodes
        }
        else
        {
            cerr << "No such node to erase.\n";
            return false; }}if(! to_delete->children[index[*beg]]) {cerr << "No such node to erase.\n";
        return false;
    }
    // Determine whether to delete the passing node that did not reach the end of the string
    else if (erase_node((++beg)--, end, to_delete->children[index[*beg]]))
        // Delete In addition to whether to delete the destination node, we also need to consider whether the last segment of the path with freq 0 can be deleted
    {
        delete to_delete->children[index[*beg]];
        --to_delete->num_children;
        // If the current node is a leaf, notify its parent to delete it
        return to_delete->freq == 0 && to_delete->num_children == 0;
    }
    return false;
}
Copy the code

C++ implementation of dictionary tree (prefix tree)Tries

Related Posts

Gikee blockchain browser -BTC ETH chain data micro increase ETC activity increased by suspected computing power attacks

Traction training what are the popular training courses

Java Concurrent Programming Notes (9) Tool Classes (5)