C++ Tries

What is a Trie? How to implement Tries in C++?

This article explains the Trie data structure and provides a sample implementation in C++.

  • Tries are used to index and search strings in a text.
  • Some examples of tries usage include, finding the longest prefix match in a routing table, auto complete of web addresses in browser etc.
  • Trie is a tree where each vertex represents a word or prefix.
  • The root represents an empty string.
  • Markers are used to indicate end of words.
  • A typical node in a trie includes the content (a char), marker for end of word and a collection of children.
  • An example of trie. (Using words Hello, Balloon, Ball)

Implementation for a Trie in C++

#include <iostream>#include <vector>using namespace std;class Node {public:Node() { mContent = ' '; mMarker = false; }~Node() {}char content() { return mContent; }void setContent(char c) { mContent = c; }bool wordMarker() { return mMarker; }void setWordMarker() { mMarker = true; }Node* findChild(char c);void appendChild(Node* child) { mChildren.push_back(child); }vector<Node*> children() { return mChildren; }private:char mContent;bool mMarker;vector<Node*> mChildren;};class Trie {public:Trie();~Trie();void addWord(string s);bool searchWord(string s);void deleteWord(string s);private:Node* root;};Node* Node::findChild(char c){for ( int i = 0; i < mChildren.size(); i++ ){Node* tmp = mChildren.at(i);if ( tmp->content() == c ){return tmp;}}return NULL;}Trie::Trie(){root = new Node();}Trie::~Trie(){// Free memory}void Trie::addWord(string s){Node* current = root;if ( s.length() == 0 ){current->setWordMarker(); // an empty wordreturn;}for ( int i = 0; i < s.length(); i++ ){Node* child = current->findChild(s[i]);if ( child != NULL ){current = child;}else{Node* tmp = new Node();tmp->setContent(s[i]);current->appendChild(tmp);current = tmp;}if ( i == s.length() - 1 )current->setWordMarker();}}bool Trie::searchWord(string s){Node* current = root;while ( current != NULL ){for ( int i = 0; i < s.length(); i++ ){Node* tmp = current->findChild(s[i]);if ( tmp == NULL )return false;current = tmp;}if ( current->wordMarker() )return true;elsereturn false;}return false;}// Test programint main(){Trie* trie = new Trie();trie->addWord("Hello");trie->addWord("Balloon");trie->addWord("Ball");if ( trie->searchWord("Hell") )cout << "Found Hell" << endl;if ( trie->searchWord("Hello") )cout << "Found Hello" << endl;if ( trie->searchWord("Helloo") )cout << "Found Helloo" << endl;if ( trie->searchWord("Ball") )cout << "Found Ball" << endl;if ( trie->searchWord("Balloon") )cout << "Found Balloon" << endl;delete trie;}
OUTPUT:-Found HelloFound BallFound Balloon