The Trie Data Structure, Part 2 (search, delete)

[@bindlessMoredom]

The other tests that get alluded to but never explained, reminds me of my time at uni. I also like hand-wavy statements like "If the code is well written..." without explaining what that means.

[@diceandbricks]

In searchtrie(), you can also loop until text[i] == '\0' instead of calling strlen().

[@tindo0038]

I believe the line 'if (cur_node == NULL) return cur_node;' in deletestr_rec is not redundant when deleting a non-existing string from the trie. Additionally, in triesearch, we should also include an initial check 'if (root == NULL) return false;' because we need to handle the case where we're searching the trie after every element inside it has been deleted.

[@galadesonne5643]

Great explanation! Pls keep doing this!

[@SriHarshaChilakapati]

I wish this video existed back in 2014 when I was in college. I had a hard time with trie back then and decided to skip it, but turned out it was very simple. Maybe I was afraid of pointers back then as I saw a lot of segmentation fault messages. Thanks for the video! And btw, I think we can keep a field for count of children in a node if we needed to optimize node_has_children function a bit (though it can increase the memory complexity). Or maybe use a set structure instead of a raw array for better comfort. Curious question, what other options do we have? Can we optimize it even further?

[@JohnHollowell]

I would leave the checks for null in the delete function as they allow to delete strings which are not in the trie. When it tries to find the child node for a unique string it will get a NULL as the child and be okay.

[@ShotgunLlama]

Will you possibly be doing a video (series) on suffix trees, suffix arrays, and their construction?

[@JacobSorber]

Maybe. I'll add it to the topic list and see what I can do.

[@maxaafbackname5562]

We once had objects where the key is a 48 bit MAC address. We store the objects in a tree the same way where each node has one bit (a LUT of two deep) of the MAC address. I didn't know the name trie at that moment, but is it functional the same, a string of (48) bits.

[@ekinigdr2030]

12:34 line 102 cries for tail recursion. Couldnt you take node as a double pointer and replace te recursiion with a loop? Again a great video!. I tried to implement a compressed version of the trie. I wonder if that would be also included in the future videos

[@icet4066]

I think your functions will cause mem leak because they create nodes in heap and do not delete them.

[@Marzex1x]

that's why we use c++

[@pierreabbat6157]

Since you put CATTLE in the trie, you should also put KINE. That would be neat.

[@MrChickenpoulet]

As always really interesting! I'm surprised we didn't learn that data structure in school, not that I encountered a situation in which it could be useful, but still, it's an interesting concept! Little suggestion, could you record your screencast in a higher FPS, would be smooth as butter!

[@RadeRarebone]

You'll hardly find any autocomplete without trie in it. :)

[@vvinoth514]

Any free resources to learn Advanced C, I mean C for Embedded?

[@Hellohiq10]

He have some embedded videos

[@vvinoth514]

@@Hellohiq10 kind of? Where?

[@Hellohiq10]

@@vvinoth514 In his channel? There is a playlist

[@leokiller123able]

In search_trie you forget to check if root is NULL

[@RmFrZQ]

I have a hard time understanding the purpose of trie data structure. I understand that you can store words and manipulate them in convenient way, but there is no real life example where trie could be useful and what is the advantage of using it over something else. For now I assume trie is a technique and you can use it to store different data objects (structures) other than single words. I wish it was explained more in the video.

[@stewartzayat7526]

It can for example be used as a dictionary for autocomplete. Firstly, you build a trie with all the possible words your dictionary recognises. Then let's say the user types "tre" and you want to give them a suggestion. So you search "tre" in your dictionary and see that it was not found. You want to find something that begins with "tre" and is in your trie. So you can simply look at the children of the node that corresponds to "tre" and see that "tree" is a child. The advantage of using a trie for this is that it is fast to look up strings. Another usage that comes to my mind, although it uses a radix trie, which is slightly different than what was shown in the video, is representation of paths to files and directories in a filesystem. I'm not sure if operating systems represent them in such a way, but it seems very natural to do so.

[@RmFrZQ]

@@stewartzayat7526 Thank you for explanation. So trie data structure is for strings only. I'll experiment with it more when I get more spare time.

[@stewartzayat7526]

@@RmFrZQ it's for strings, but strings don't necessarily have to be strings of characters. It could be strings of anything.

[@johnnysummers9323]

I'm pretty sure you already know this but when you search something for instance here on KZbin the suggestion it gives a probably implemented on a Trie... Any kind of search bar the suggests a word is probably using a trie.

[@mihaicotin3261]

It is good for autocomplete words and typing sugestion i believe

[@vvinoth514]

❤️from India