How to implement trie in C++

📅 2015-Nov-02 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ cpp, trie ⬩ 📚 Archive

Trie, also known as prefix tree, is an elegant and efficient data structure to use as a symbol table for keys that are strings. In a trie, the number of accesses required to search or insert a string is linear in the string length. In fact, it is just one more than the number of characters in the string.

Sedgewick’s Algorithms textbook has a particularly elegant trie implementation in Java. I created a similar C++ version just for fun here:

// Adapted from Trie code in Algorithms (4 Ed) by Sedgewick

#include <iostream>
#include <string>

// Size of alphabet
constexpr int R = 256;

struct Node
{
    Node*       next_[R] = {};
    std::string val_;
};

class Trie
{
    public:

    void Put(const std::string& key, const std::string& val)
    {
        root_ = Put(root_, key, val, 0);
    }

    std::string Get(const std::string& key)
    {
        Node* x = Get(root_, key, 0);

        if (!x)
            return "";

        return x->val_;
    }

    private:

    Node* Put(Node* x, const std::string& key, const std::string& val, int d)
    {
        if (!x)
            x = new Node();

        if (d == key.size())
        {
            x->val_ = val;
            return x;
        }

        char c      = key.at(d);
        x->next_[c] = Put(x->next_[c], key, val, d + 1);

        return x;
    }

    Node* Get(Node* x, const std::string& key, int d)
    {
        if (!x)
            return nullptr;

        if (d == key.size())
            return x;

        char c = key.at(d);

        return Get(x->next_[c], key, d + 1);
    }

    Node* root_ {};
};

int main()
{
    Trie t;
    t.Put("cat", "feline animal");
    t.Put("rat", "eaten by cat");

    std::cout << t.Get("rat") << std::endl;
    std::cout << t.Get("cow") << std::endl;

    t.Put("rat", "a rodent");

    std::cout << t.Get("rat") << std::endl;

    return 0;
}