How to implement trie in C++

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;
}

view raw
trie.cpp
hosted with ❤ by GitHub

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.