📅 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
{next_[R] = {};
Node* 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)
{root_, key, 0);
Node* x = Get(
if (!x)
return "";
return x->val_;
}
private:
const std::string& key, const std::string& val, int d)
Node* Put(Node* x,
{if (!x)
new Node();
x =
if (d == key.size())
{val_ = val;
x->return x;
}
char c = key.at(d);
next_[c] = Put(x->next_[c], key, val, d + 1);
x->
return x;
}
const std::string& key, int d)
Node* Get(Node* x,
{if (!x)
return nullptr;
if (d == key.size())
return x;
char c = key.at(d);
return Get(x->next_[c], key, d + 1);
}
root_ {};
Node*
};
int main()
{
Trie t;"cat", "feline animal");
t.Put("rat", "eaten by cat");
t.Put(
std::cout << t.Get("rat") << std::endl;
std::cout << t.Get("cow") << std::endl;
"rat", "a rodent");
t.Put(
std::cout << t.Get("rat") << std::endl;
return 0;
}