Tries are a lesser known, but very useful data structure. A trie (or prefix tree) is an ordered tree data structure, such that each descendant of a given node in a trie share a common prefix. This property makes for fast prefix based queries (used in auto complete, spell check, etc.).
A trie with words a, at, ate, on, one, out, my, me, and mud. Filled in nodes denote the end of a word.
Implementing a trie is similar to implementing any other n-ary tree, with a few key differences.
Each node in a trie has a set of outgoing edges labeled by a character. Each node must also contain a flag indicating whether it is a valid word end.
Outgoing edges can be represented by a map of
char => node*.
n[c] => m denotes that n has an outgoing edge labeled c, incident on m.
The end of word marker can be represented trivially by a boolean field.
Our node ends up looking like this:
As with most tree-like structures, the only data member required for a trie is a node which points to the root.
To insert into a trie, you simply iterate through the input string and walk the corresponding edge labels. If a given edge does not exist, create it. Once you have exhausted the input string, mark the node you ended on as a valid end of word.
Since tries have no cylces, we were able to use unique_ptr everywhere, and thus do not need to worry about explicity freeing any memory assoicated with our trie.