0

I am so completely lost. I completed PSET5 with a hash table, and the concept of hash tables makes sense to me. Now I am attempting to do it with a trie, and I am just so confused I don't even know where to start. I have watched the videos several times and searched for resources online, but I suppose I'm not asking the right questions, because I can't find much information on them.

I don't even understand the objective of a trie. With a hash table, it makes intuitive sense - take a word, store it in a node, chain those nodes together into a linked list, put them in a hash table, then you can access each node by hashing a word and traversing the linked list. With a trie, what is being stored? How can one "load" a dictionary? How is the boolean is_word related at all to retrieving the word?

I suppose this is a stupid question. I would really like to understand this but I'm so completely confused I don't even know where to start. I have absolutely no clue. Could someone shed some light onto this, or point me to some resources that might help? Thanks.

3

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[0], 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[0]->next[23] or, if you're using a cursor, the last pointer would be cursor->next[23].

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[2]->next[0]->next[19] and root->next[2]->next[0]->next[19]->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. ;-)

3
  • Cliff, thank you for taking the time to answer my question. I'm still very lost. Some of what you wrote makes sense, but I can't understand how to translate that into my code. Is there any way that I could have you look over my code? I'm sort of embarrassed to share it on here. Thanks – jermriddled Apr 5 '19 at 20:13
  • I am also active on CS50 Slack. You can send it to me privately there. cs50x.slack.com I believe that there's an open invitation on the CS50x website that describes all of the available forums. – Cliff B Apr 5 '19 at 22:44
  • Thanks so much Cliff, I really needed your more detailed explanation. – Claire Jul 13 '20 at 9:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .