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

  Рет қаралды 13,053

Jacob Sorber

Jacob Sorber

Күн бұрын

Пікірлер: 27
@bindlessMoredom
@bindlessMoredom 3 жыл бұрын
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
@diceandbricks 3 жыл бұрын
In searchtrie(), you can also loop until text[i] == '\0' instead of calling strlen().
@tindo0038
@tindo0038 4 ай бұрын
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
@galadesonne5643 2 жыл бұрын
Great explanation! Pls keep doing this!
@icet4066
@icet4066 2 жыл бұрын
I think your functions will cause mem leak because they create nodes in heap and do not delete them.
@Marzex1x
@Marzex1x 7 ай бұрын
that's why we use c++
@SriHarshaChilakapati
@SriHarshaChilakapati 3 жыл бұрын
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?
@ShotgunLlama
@ShotgunLlama 3 жыл бұрын
Will you possibly be doing a video (series) on suffix trees, suffix arrays, and their construction?
@JacobSorber
@JacobSorber 3 жыл бұрын
Maybe. I'll add it to the topic list and see what I can do.
@JohnHollowell
@JohnHollowell 3 жыл бұрын
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.
@pierreabbat6157
@pierreabbat6157 3 жыл бұрын
Since you put CATTLE in the trie, you should also put KINE. That would be neat.
@maxaafbackname5562
@maxaafbackname5562 2 жыл бұрын
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.
@MrChickenpoulet
@MrChickenpoulet 3 жыл бұрын
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
@RadeRarebone 3 жыл бұрын
You'll hardly find any autocomplete without trie in it. :)
@ekinigdr2030
@ekinigdr2030 3 жыл бұрын
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
@vvinoth514
@vvinoth514 3 жыл бұрын
Any free resources to learn Advanced C, I mean C for Embedded?
@Hellohiq10
@Hellohiq10 3 жыл бұрын
He have some embedded videos
@vvinoth514
@vvinoth514 3 жыл бұрын
@@Hellohiq10 kind of? Where?
@Hellohiq10
@Hellohiq10 3 жыл бұрын
@@vvinoth514 In his channel? There is a playlist
@RmFrZQ
@RmFrZQ 3 жыл бұрын
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
@stewartzayat7526 3 жыл бұрын
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
@RmFrZQ 3 жыл бұрын
@@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
@stewartzayat7526 3 жыл бұрын
@@RmFrZQ it's for strings, but strings don't necessarily have to be strings of characters. It could be strings of anything.
@johnnysummers9323
@johnnysummers9323 2 жыл бұрын
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
@mihaicotin3261 Жыл бұрын
It is good for autocomplete words and typing sugestion i believe
@leokiller123able
@leokiller123able 2 жыл бұрын
In search_trie you forget to check if root is NULL
@vvinoth514
@vvinoth514 3 жыл бұрын
❤️from India
Working with a Matrix/2D Array in Your C and C++ programs.
23:40
Jacob Sorber
Рет қаралды 36 М.
The Trie Data Structure (Prefix Tree)
21:07
Jacob Sorber
Рет қаралды 82 М.
Farmer narrowly escapes tiger attack
00:20
CTV News
Рет қаралды 11 МЛН
Trie data structure - Inside code
13:26
Inside code
Рет қаралды 10 М.
How does fork work with open files?
13:12
Jacob Sorber
Рет қаралды 10 М.
Student programmers, ChatGPT is not your friend
13:46
Jacob Sorber
Рет қаралды 12 М.
What is the Trie data structure and where do you use it?
15:04
Gaurav Sen
Рет қаралды 108 М.
Fixed and Variable Length Arrays in C and C++
20:24
Jacob Sorber
Рет қаралды 45 М.
Implement Trie (Prefix Tree) - Leetcode 208
18:56
NeetCode
Рет қаралды 213 М.
Why are Progress Bars Always Wrong? Progress Bar Example in C.
35:44
Premature Optimization
12:39
CodeAesthetic
Рет қаралды 835 М.