Don't feel bad, it took me a little while to wrap my head around the concept originally. ;-)
A trie is essentially a tree representation of a bunch of words. The root of a tree and every node can potentially point at up to 26 nodes, but let's keep it simple. Say that you have to build a trie with 3 words, "am", "at", and "ad". When the trie is finished, the root will have a root->next pointer that contains the address of the "a" node. Moving down the trie, the "a" node would have next pointers to the "d", "m", and "t" nodes. Since each of these nodes is the end of a word, they would also have the is_word flag set to true. Note that these nodes could also point at other words. For example, if a trie had the words cat and cater, the t node would show is_word = true and would have a pointer to the "e" node on the next level.
That's a brief description of how a trie looks. Here's the part that is probably confusing you. It's natural to think that the actual letter or the word should be stored somewhere. It's obvious, isn't it?
Well, no. In a trie, you don't store the letter or the word (unless you really want to). The key fact is that the EXISTENCE of a node represents the letter. Take the trie above. Now, imagine checking for the existence of the word "ax". The process is simple. Go to the root and check the next pointer to "a". It has an address stored, so the letter a as the first letter exists. You then go to that "a" node, which was probably the address stored in
root->next, and check the pointer to the "x" node. This time, the node is set to NULL, meaning that the node for that letter doesn't exist. THAT means that there is no word starting with "ax". By the way, the full path to the x would be
root->next->next or, if you're using a cursor, the last pointer would be
So, the secret is that the existence of a series of nodes represents the existence of a word. Extending the descriptiion, "cat" would be represented by the node string of
root->next->next->next->is_word = true. The actual words or letters themselves aren't stored anywhere.
Hopefully, this fills in the blanks for you. IF you have more questions, please post a comment.
If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)