Game Development Reference
In-Depth Information
{
private:
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
found.
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 )
{
return;
}
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;
}
else
{
auto tmp = std::shared_ptr<node>(new node(character));
current->push_back(tmp);
current = tmp;
}
if ( i == word.size() -1 )
{
current->MarkWord();
}
}
}
The main part of the algorithm iterates over every character in the word we wish to insert
intothetrie;duringtheiterationwesearchthecurrentnodetoseeifthecharacterisalready
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,
