Create a trie class for search suggestions
A trie, sometimes called a prefix tree, is a type of search tree, commonly used for predictive text and other search applications. A trie is a recursive structure designed for depth-first searches, where each node is both a key and another trie.
A common use case is a trie of strings, where each node is a string in a sentence. For example:
Figure 11.1 – A trie of strings
We often start a search at the head of a trie, looking for sentences that begin with a specific word. In this example, when I search for all, I get three nodes: you, the, and along. If I search for love, I get me and is.
A string trie is commonly used for creating search suggestions. Here we will implement a string trie using std::map for the trie structure.
How to do it…
In this recipe, we create a recursive trie class that stores nodes in a std::map container. It's a simple solution for a small in-memory trie. This...
