The Trie Data Structure (Prefix Tree)

Подписаться 161 тыс.

Просмотров 75 тыс.

50% 1

Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
The Trie Data Structure (Prefix Tree) // Move over hash tables, you've got some competition. This video talks about the Trie data structure (also known as a prefix tree) and shows you how to implement it in C.
***
Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.
About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.
More about me and what I do:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]

Опубликовано:

24 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 123

@oj0024 3 года назад

I recently learned about another awesome data structure called "random skip list".

@2005kpboy 2 года назад

Redis uses skip-lists for internal implementation of sorted sets

@TheCocoaDaddy 3 года назад

Great video! I had never heard of a Trie data structure before. Thanks for posting!

@JacobSorber 3 года назад

You're welcome. Glad I could add something to your repertoire.

@KamillaMirabelle 3 года назад

The size of the lookuptable are the miminum size we need to represent all representable encoding. This is the same for lexer based on DFA, since all encoding bigger than 8bit pr. Codepoint are just a sequence of bytes which we can search with.

@manohars123 11 месяцев назад

Informative and well explained, Thanks! One optimization suggestion - In trieinsert( ) function, once child node with NULL is reached, no need to further check for NULL as it would always be the case.

@trimethoxy4637 3 года назад

omg really helpful. I was about to ask you to make video covering this topic, but you overtook me! going to create dictionary inside trie

@JacobSorber 3 года назад

Glad I could help. Lots of requests for this topic.

@R4ngeR4pidz 3 года назад

Awesome, love learning new things from your videos :P

@JacobSorber 3 года назад

Thanks, Thijs. I'm glad they're helpful.

@itsbk6192 3 года назад

Lets gooooo, i'll trie to keep a hold of my excitement

@mohamedhussien4013 Год назад

Thank u so much. Elegant code.

@sneakypete765 3 года назад

Thanks for another great video!

@JacobSorber 3 года назад

Glad you enjoyed it!

@Vulto166 Год назад

Man you really wake up early! 5pm :O Thanks for the content!!

@jordanchen23 3 года назад

I've recently learned how to write a working trie dictionary program and your videos on linked lists and mmap have been tremendously helpful. That being said, I'm currently trying to optimize my code and learning a lot about cache profiling in the process since my program's still takes a long time to load an entire dictionary file. Maybe it's just because my own implementation used 27 child nodes, and the size of my data structure is leading to a lot of cache misses that I don't know how to resolve.

@JacobSorber 3 года назад

In addition to cache profiling, have you used a standard code profiler, to see where your program is spending most of its time? That might help you identify any bottlenecks. But, yes, the larger your trie nodes are, the worse I would expect your cache performance to be.

@jordanchen23 3 года назад

@@JacobSorberIf you're mean time taken for each part of my trie implementation, then no. Do you have any specific recommendations for profilers? However, if you mean the net runtime of each discrete stage in overall execution (load, check, unload), then yes. My assignment has a prewritten timer function in the main program file. For a dictionary with 143,091 words (max length 45 characters), it takes 0.08 secs to insert everything into a trie structure that contains 27 child nodes. Thing is, it only takes 0.04 seconds to unload everything, and while I do realize that it's easier to free memory I still found the asymmetry rather strange.

@sumitbhosale3401 3 года назад

Nice One. Thanks

@rohankokatanur6426 3 года назад

I learnt just a week ago that tries exist and thought to learn about them ..... You drop a video on it ...🎉

@JacobSorber 3 года назад

Nice. Glad the timing worked out well.

@thejedijohn 3 года назад

Excellent explanation. Thank you for this. I'd recommend setting a higher delay before the code completion suggestions pop up, they were very distracting and made it much harder to follow the code. But maybe that's just me and my anxiety acting up.

@recursion. 2 года назад

Nah just rewind it

@StephenBeale Год назад

This was excellent, thank you. Just one bit of feedback - often you are working quite low on the screen, which can be frequently obscured on RU-vid by the player controls along the bottom if (like myself!) the viewer is having to pause often in order to keep up. Cheers.

@jordanchen23 Год назад

I'm trying to make a trie that uses calloc to request a large amount of memory ahead of time and allocate them as needed.. A memory bucket if you will that can be called anytime the current one gets used up. The point is to lower the overall number of memory requests in the program. But i can't figure out the proper declaration of a ptr to a single trienode that allows me to to access and manipulate an array of trienodes that's already part of structure.

@JesseSabatini 2 года назад

greate video! not sure what i did wrong, i copied verbatim from the code in the video and i segfault in the insert for loop when calling insert on the second word. I used some debugging printf's and noticed that when inserting cattle, memory exists where it should be NULL causing it to bypass the new node creation within the insert for loop's if statement. not sure how i messed up tbh

@user-tq1rr1tc2c 2 месяца назад

ممنونم استاد

@Elzelgator 2 года назад

Do we need to dynamicly allocate when we create a new Node??

@matiasbpg 3 года назад

Nice video!

@JacobSorber 3 года назад

Thanks! Glad you enjoyed it.

@evansngugi2238 3 года назад

Fantastic

@JacobSorber 3 года назад

Thanks.

@birajpatel2804 3 года назад

Hi sir. Can you do a video explaining how to implement JavaScript's setTimeout & clearTimeout in C? Thank you!:)

@JacobSorber 3 года назад

Oooh. Good idea. I'll add it to the topic list and see what I can do. Thanks!

@ash1992saga 2 года назад

I didnt understand the printtrie_rec function why the memcpy was done and how did he retrive the strings in the proper ascii alphabetical order ? Someone pls helpp me understand this .

@Cosm1nx 3 месяца назад

my saviour

@ekinigdr2030 3 года назад

We can use that structure to sort numbers right ? I was messing around with it and i realized if i put random numbers and print breadth first fashion i get them in a sorted order.thanks by the way for all the videos youve created

@JacobSorber 3 года назад

Yes, you definitely can. The sorted nature of the trie is one of the main advantages over something like a hash table. And, you're welcome. I'm glad you're enjoying them.

@gregoryfenn1462 3 года назад

Doesn't line 14 at 8:15 raise an error as you are using newnode (in the right-hand express) before defining it? How does malloc know what side to allocate if newnode isn't defined yet?

@diceandbricks 3 года назад

Newnode is defined. Compiler parses the statement left to right, even though the code evaluates malloc before the assignment. This is a common idiom.

@lllbenderlll 3 года назад

WoW Man!!! This is nice 👍!!!

@JacobSorber 3 года назад

Thanks! Glad you like it.

@lllbenderlll 3 года назад

@@JacobSorber it Would be very nice if you do a playlist with all your "data structures" videos. I like your style of explanation, it's awesome!!!

@satriohalim7213 2 месяца назад

Hi Jacob, just wanna say your video is amazing and really helped me to learn Trie Data Structures. If i could ask, can you help me with printing words that starting with a certain prefix word? like print words starting from "da". I'm new in this thing and sometimes getting confused. I will be very gratefull if you can aswer me. Thank You Jacob!.

@laugh_till_u_pee968 3 года назад

i just subscribed to your channel for C language related content, but im commenting here just so you know, you are making great content. keep up the great work. subscribers will come eventually.

@JacobSorber 3 года назад

Welcome! And, thanks for the support.

@MKhan-eq6pj 3 года назад

Man you're a great guy. Could you do an algorithms playlist? Like a course like playlist! that would help so much and of course do it in C plsss

@JacobSorber 3 года назад

Thanks. I'll see what I can do.

@godfather7339 3 года назад

@@JacobSorber 1 second him, I love ur teaching style

@KFlorent13 3 года назад

@@JacobSorber Do you have any plan to tackle how to properly decompose your program ? What I mean is that I constantly seem to create circular dependencies with my .h files which are quite annoying to get rid of...

@guangtingyu5609 3 года назад

Question: you don't free the memory after calling malloc, does that cause a memory leak?

@diceandbricks 3 года назад

Depends. The OS automatically frees all resources when the process ends. For a short-lived process like this, the programmer can rely on the OS to perform that clean-up. A long-running process should manage and free its own resources.

@mikelong3444 2 года назад

🔥🔥🔥

@JMoloneyProjects Год назад

Since when can you dynamically assign a buffer length at runtime? unsigned char buffer[length + 1]; (When length is an unknown to the compiler function argument)? In my experience this should hit a compiler error. Am I missing something?

@JacobSorber Год назад

C99, but the rules were adjusted further in C11, I think.

@JMoloneyProjects Год назад

@@JacobSorber That's cool, C++ needs to take note. Just tried in C++17 and it says no. How exactly doe it work? It couldn't put it onto the stack because it doesn't know how large it is to pre-allocate it. Does it write the code to malloc and free in the compiler?

@BookofYAH777 Год назад

1:20 "now we got it sorted out and we just call them tries" but then you can't distinguish it from "try" statement

@JacobSorber Год назад

True, but at least a try statement isn't a data structure, so maybe we can use context clues to figure out what we're talking about.

@BookofYAH777 Год назад

@@JacobSorber that makes sense

@junbird 3 года назад

8:25 Why not use calloc instead of malloc, so that the array would already have been initialized to NULL values, without the need of manually looping on it? By the way, really great video, I would guess that this data structure is basically what Java refers to as "TreeMap", right? Like, you could replace that boolean with a pointer to something and if the pointer is NULL, the map doesn't contain that symbol, otherwise it returns that pointer (or something like that).

@jordanchen23 3 года назад

I tried doing it this way for my first trie program and it worked, but when you run valgrind it reports memory leaks. The reason is seems to be that calloc sets all the values to 000000000000s, which isn't the same as NULL. As such, you must initalize all the pointers in a node to NULL unless you're using that memory block to read what's already in a file. So although calloc gives you a nice whole chunk of memory, you still have to do the looping, and the time you'd need to initilaize all the child nodes to NULL would probably end up taking longer than if you just used malloc in the first place.

@junbird 3 года назад

@@jordanchen23 mhm really? I really don't get why though, isn't NULL in C just an alias for 0?

@jordanchen23 3 года назад

@@junbird correct me if I'm wrong, but ptrs are technically only instructed to "select" one byte at a time, specifically the 0th byte of whatever datatype the ptr itself is representing. What happens when your ptr requests memory is that the compiler will return to it the specified length of addressable memory space which is supposed to be off-limits to any unrelated processes hereafter. But until you set each data-containing part of the ptr-to-struct to null, anything within those spaces will remain as garbage value. Therefore, there is no guarantee that a program won't accidentally overwrite these spaces, so the compiler will just flag these as problems unless told otherwise.

@viacheslav1392 Год назад

@@junbird null isn't necessary 0

@jamalhasan6624 Год назад

@@junbird null is 0x0

@klarnorbert 2 года назад

Can you do one about radix tree?

@JacobSorber 2 года назад

Probably. I'll add it to the list. Thanks.

@NeigeFraiche 3 года назад

Instead of bool trieinsert(**trienode, ..), why not pass *root by ref? ie trienode *&root

@virajdesai2955 3 года назад

Passing by reference like that is a concept only in C++, not C.

@benjaminshinar9509 3 года назад

wait, what? in the recursive function, did you really declare an array on the stack with a variable length? how does that work? I thought it was illegal to do, doesn't that mess up the stack frame size?

@fgdou 3 года назад

No, he declares an array on the heap (malloc), but he forgot to free it Sorry to disappoint you 😁

@benjaminshinar9509 3 года назад

@@fgdou I'm asking about line 48, in the print_trie recursive function.

@diceandbricks 3 года назад

@@benjaminshinar9509 yes Variable Length Arrays are legal in C99. It dynamically allocates array on the stack and automatically cleans up. It only works in function scope, not global nor static. Jacob might have a video about it. My advice is use them sparingly and with caution. If you make the array too large it can fill up your stack space.

@benjaminshinar9509 3 года назад

@@diceandbricks oh that explains it. I learned strict Ansi89 C before moving on to other languages.

@emanalsbeiheen5619 3 года назад

What is the best IDE for C langauge?,,,,, and Thank you for this great content

@_tobii 3 года назад

Its subjective. It depends on what you need It to do

@DFPercush 3 года назад

Visual Studio (not Code) community edition if you're on Windows, for Linux probably Code::Blocks, maybe Eclipse, I'm not sure if IntelliJ does C but that's another one. I'm sure a decent search engine will turn up a few results with pros and cons, but tbh I find Visual Studio's debugger integration hard to beat.

@emanalsbeiheen5619 3 года назад

@@DFPercush Thank you

@emanalsbeiheen5619 3 года назад

@@_tobii I just wanna learn data structure with C,, Im Android developer

@_tobii 3 года назад

@@emanalsbeiheen5619 are you working on Linux?

@nicholas_obert 3 года назад

Nice to see you always use make even for dirt simple projects.

@JacobSorber 3 года назад

It's a good habit.

@mhamdmarch8709 3 года назад

You are amazing pls dont stop uploading videos 😍😍😍🤩🤩🤩🤩😘😘😘😘😘😘😘 Love u sooo much

@JacobSorber 3 года назад

Thanks.

@JohnHollowell 3 года назад

in createnode(), shouldn't it be mallocing a "sizeof trienode" and not "sizeof *newnode"? It should be the size of the struct (and not a pointer to that struct) and should also be the trienode type and not the newnode variable. I didn't even know you could use sizeof with a variable

@thetastefultoastie6077 3 года назад

newnode is a pointer to a trienode Therefore dereferencing the pointer with the Dereference Operator '*' results in a trienode type So sizeof(trienode) and sizeof(*newnode) are equivalent The advantage to using the type of the variable, instead of using the type directly, is that if you can change the type of the variable, you don't need to update the typeof statement

@JacobSorber 3 года назад

Right. What Mr. Tasteful Toastie said.

@JohnHollowell 3 года назад

totally makes sense. I was thinking of it as a pointer and not dereference. Gotta love C's overloading of the * symbol for multiple things

@Timz2U 3 года назад

Great tutorial again! BTW, could you please make your code at the center of the screen in the next video? The subtitle just overlaps the code ;)

@Timz2U 3 года назад

oops, I just realized the subtitle is movable

@OlliS71 Год назад

Better program such Things in C++, it's more descriptive if you use the OOP features and you could casually teach some generic programming in this case. I think the most common trie data structure is the mapping trie which every memory management unit of modern CPUs has. The speciality with that is that the prefix-length of each branch at the same level has the same number of bits.

@user-he4ef9br7z 3 года назад

Can somebody tell me more about stdbool? I'm new to C.

@auz7977 3 года назад

essentially, C (unlike some other languages) doesn't have a boolean data type built into the language itself. most of the time, people would use an integer with a value of 1 to mean "true", and 0 to mean "false". stdbool is a part of the standard library that adds a bool data type as well as "true" and "false" macros to use with it. so instead of writing something like this: int someCondition = 1; // 1 means true with stdbool, you can do this: bool someCondition = true;

@thetastefultoastie6077 3 года назад

@@auz7977 Actually, C99 added a builtin boolean type called _Bool, and guarantees that any two true values will compare equal (which was impossible to achieve before) So stdbool.h doesn't add a boolean data type, but it does have these defines: #define bool _Bool #define true 1 #define false 0 #define __bool_true_false_are_defined 1

@auz7977 3 года назад

@@thetastefultoastie6077 this is true. i just thought it would be easier to explain stdbool without having to explain _Bool. imo, using _Bool without stdbool is almost pointless. although i suppose i could have explained a bit better.

@thetastefultoastie6077 3 года назад

@@auz7977 oh ok. I've met some seasoned C software engineers who didn't realise C had real booleans. Just nice to know it's a thing.

@SimGunther 3 года назад

Wait until you see what hash array mapped tries and its cousin CHAMP have in store for you! :D

@JacobSorber 3 года назад

I know. The fun never ends. 😂

@pierreabbat6157 3 года назад

Trie it, you'll like it.

@JacobSorber 3 года назад

😀

@SeshachalamMalisetti 2 года назад

type struct Node { Children map[rune]*Node }

@cmdlp4178 3 года назад

create_code could have been just a simple call to calloc, that already initializes all members to 0 Also, the stack memory used is O(k²), where k is the trie-depth

@TheRealLughnatic 3 года назад

I think malloc is better in this case, since viewers may want to port this to other languages, and it may not seem immediately obvious how to port calloc to another language.

@nephatrine 2 года назад

I always have pronounced it like "tree".

@argustuft 2 года назад

Does anybody still use Patricia tries ?

@argustuft 2 года назад

When I looked at Patricia tries (many years ago) I couldn't find a robust way of deleting nodes, so this limited their use. Great method for string searching and hash tables. It would be a good subject for Jacob to address.

@argustuft 2 года назад

Patricia allows fixed size nodes with variable length strings node: (leftptr,rghtptr,bitindex,strgptr)

@KamillaMirabelle 3 года назад

Have you considered to move to rust?

@muhammadwasim8787 3 года назад

Just wishing if we get it implemented in java.

@fgdou 3 года назад

Ho no! You forgot to free the array in the recursive function! 😂

@Mozartenhimer 3 года назад

Don't need to, it's allocated on the stack.

@casperes0912 2 года назад

I can't get over the fact that you place the pointer-stars in the wrong place. int* name is so much cleaner than int *name. Yes it goes wonky if you have multiple assignments on one line, but I don't think that's good to do in general in the first place, at least not if you're mixing pointers and values. int* says "this is an integer pointer" int *name says "This is an integer........ oh yeah, just a pointer to it" I can even accept int * name. In that case it can be seen as a qualifier similar to long int or unsigned int. Just space add extra type info. It is also more consistent with the way you cast things (unsigned char *) - the pointer-star is itself a free-standing bit of information, not tied to the name. But that's just me. Everyone has their own view on this I guess :)

@rustycherkas8229 2 года назад

Wrong place??!! typedef struct { int foo; int bar; } myStruct_t, *ptrMyStruct_t; The variable - not the datatype - is the pointer. One cannot extend "int* name;". One CAN extend "int *name;" to "int *pVar1, *pVar2;" Time to "get over" it if you want to write good 'C' code.

@lewiscole5193 3 года назад

Professor Sorber is obviously trying to introduce what tries are to neophyte programmers. But as with any data structure, it's important to understand the advantages and disadvantages of the use of any particular data structure to know when it's appropriate to use one versus another. So FWIW, let me emphasis what Professor Sorber waved his arms at, namely that tries are good for data retrieval, but they get there from here usually at the cost of using more memory to gain speed. But there are some instances where hash tables can beat tries when it comes to look up speed without the higher memory cost and if you want to do something other than exact string look up, say like partial string look up or sorting strings in addition to just trying to retrieve them, then some other form of tree like a ternary tree might be a better choice than a trie. Just for giggles, if anyone is interested in ternary trees, here's a paper that describes using ternary trees for searches, sorts, and partial string searches: < www.cs.princeton.edu/~rs/strings/paper.pdf >i