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 #include // 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

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