The so-called trie data structure poses an interesting way to store data in an easily searchable manner. When segmenting sentences of text into lists of words, it is often possible to combine the first few words that some sentences have in common.
Let's have a look at the following diagram, where the sentences "hi how are you" and "hi how do you do" are saved in a tree-like data structure. The first words they have in common are "hi how", and then they differ and split up like a tree:
Because the trie data structure combines common prefixes, it is also called prefix tree. It is very easy to implement such a data structure with what the STL gives us already. This section concentrates on implementing our own trie class.
