cant wrap my head around implementing this trie

Question

So in theory the concept of a trie makes a lot of sense, but I'm really missing something when it comes to putting it down into code. Any help would be soooo greatly appreciated. I've scoured the internet for help but still missing a few connections. Ok... Here's what i'm getting... or think i am. Sorry this is gonna be long...

First off children[0] doesnt hold any actual value at that index right? its literally just a pointer. So 'a' doesnt actually exist anywhere other than that its essentially children[a]?

You create and malloc a root node, the is_word bool is false and the children pointer isnt pointing anywhere.

Then you create a new node that equals the root...

Then you iterate over the word to input the characters one at a time...

If the character is a letter or ' then you create/malloc a new node and the is_word is still set to false.

When you reach the last letter of the word you change is_word to true... that is essentially adding \0 right? (Also, instead of checking for NULL would saying if i == length of the word work?)

That potentially takes care of one word in the trie... I cant figure out how then to start another one. is it literally the same thing? and the way you find different words is just by seeing if the index of children is null? if so there's no letter if not then keep checking for null until you find is_word = true?

Typing this out helped a bit but still confusing.. Thanks for the help!

Answer 1

First off children[0] doesnt hold any actual value at that index right? its literally just a pointer. So 'a' doesnt actually exist anywhere other than that its essentially children[a]?

you probably get that correctly, but just to put it in a more suitable form:

• yes children[i], where i is a valid index, is a pointer. a pointer may hold a value (a memory address).
• no, 'a' doesn't have to physically exist.
• children['a' - 'a'], aka children[0], (not children[a]) is a pointer to a trie node that may represent an 'a' (or an 'A').

You create and malloc a root node, the is_word bool is false and the children pointer isnt pointing anywhere.

ideally, the root itself should be an array of pointers to trie nodes. each trie node being pointed to by one of these pointers should represent an alphabetical character as the first character in a word.

for example, the trie node pointed to by root['a' - 'a'] should represent an 'a' (or an 'A') as the first character of some word, the trie node pointed to by root['b' - 'a'] should represent a 'b' (or a 'B') as the first character of some word, and so on.

each trie node should have an array of children (also pointers to trie nodes) and a boolean flag that should be set to true, if the character that this trie node represents is an end of a word.

as I just mentioned, the array of children should be an array of pointers to trie nodes as well. each trie node being pointed to by a pointer in that array represents an alphabetical char or an apostrophe as the character following the parent in a word.

this may be a little confusing, so here is an example:

root['h' - 'a'] // points to trie node that represents 'h' as first char in a word
root['h' - 'a']->children['i' - 'a'] // points to trie node that represents 'i' 
                                     // as second char, after 'h', in a word

if you have memory allocated for root['h' - 'a'] and root['h' - 'a']->children['i' - 'a'] (i.e., both are not NULL pointers, assuming you initialize them with NULL once they're defined), and root['h' - 'a']->children['i' - 'a']->isWord is true, that means that you have the word "hi" in your trie.

---

How to insert a word in a trie?

to insert a word in a trie, you do the following:

calculate index of first char in word to be inserted
define a temporary pointer to trie node to act as cursor
set cursor to point to node that represents the 1st char // as in cursor = root[index]

do
    ensure cursor has memory allocated for it

    if current char is last char
        mark node pointed to by cursor as an end of word
        break
    else
        calculate index of next char

        update cursor to point to node that represents next char
        // as in cursor = cursor->children[index]
while true

hope that clears any confusion! for more, watch the short on tries: https://youtu.be/TRg9DQFu0kU!