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