Game Development Reference
In-Depth Information
wchar_t m_character;
bool m_isWord;
size_t m_index;
std::vector<std::shared_ptr<node>> m_children;
The node is keyed with the character it represents, this is not strictly necessary and may
be adapted to serve more general purposes. The children are stored in a vector of nodes,
this will make iterating over them straightforward using the m_index member. Finally,
m_isWord is a flag that we will set when a node may be considered a full word, this is
useful to know when we can stop iterating through children nodes and return what we've
Before we look further inside the node, let's take a moment to analyze the algorithm used
to add a word into our trie.
void trie::add(const std::wstring word)
if ( word.size() == 0 )
std::shared_ptr<node> current = m_root;
for ( size_t i = 0; i < word.size(); ++i )
wchar_t character = word.c_str()[i];
auto child = current->find(character);
if ( child != nullptr )
current = child;
auto tmp = std::shared_ptr<node>(new node(character));
current = tmp;
if ( i == word.size() -1 )
The main part of the algorithm iterates over every character in the word we wish to insert
a child within it, if it is, we set the node we found as our current node and we continue it-
erating untilwereachapointinwhichwedon'tfindanode.Ifthecharacter doesnotexist,
Search WWH ::

Custom Search