The Trie →
In a previous post we started with some motivation for the need of a tree like data structure for efficient prefix matching. We will see how to implement Trie in C++ in this post.
Trie is a tree data structure made up of nodes that contain some data. So, we need to design a structure for the nodes and some structure fields for storing the data. Since we are talking about prefix strings and strings are made up of characters, we can think of a node as having a hashmap, storing the prefix character and a reference to the Trie node holding the remaining characters (children nodes). We can go about defining a structure like this:
The boolean variable isLeaf
is to indicate the end (leaf node) of the string in the Trie. And when we start populating a new Trie, we need to allocate a new structure, something like the following newTrieNode()
. We set the isLeaf
to false
as we need to set this to true
only for leaf nodes.
We can also write a small function to check if a node has any children (by checking the value of isLeaf
).
We will look at populating a Trie by inserting characters from a string into the Trie, as well as searching for a prefix in a future post.