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

hey everybody today we're going to finish up our conversation about tries a data structure for storing searchable sorted sets of symbolic [Music] strings hey folks welcome back sorry for the last videos cliffhanger today we're going to finish up our tri data structure if you didn't see the previous video you should check it out if you have no idea what trees are or tries or look up tables or any of the things that build up to this or if this video feels like a conversation that you're joining in the middle there are a bunch of other videos you might want to check out i'll put links down in the description feel free to pause this video go watch those and then come back you might have a better experience source code as always is available through patreon and the source code for this video is basically half done because we started it in the previous one so last time we talked about tries and we started building one here is the code that we were looking at here let me adjust this down a little so just a quick recap we defined our node structure here and we created functions that will create nodes and we'll insert a string into our try and we also made a recursive function down here that would print out our try okay and then down here in main we just created one and we just tested it out we inserted a couple of things and we printed out our try and it all seems to work what we didn't do is we didn't add search and we didn't add delete and so those are the two things that i want to add today to our implementation so search of course is critical since that's the main point of a try the whole the tried name actually comes from retrieval the whole point is to actually like find out whether something is in a try or not we want to be able to quickly find out whether or not a particular string is in our sorted set of searchable symbolic strings and so today we want to make a function to do that so let's make a search function uh let's have it return a bool that's going to be true if it's in there and false if it's not we'll call this search try and we're going to pass in a try node that's just a node to our tree it's going to be the the root and then we're going to pass in our signed text now this you would have noticed from the last time basically the reason for the sign text is purely because we want we're going to convert this to unsigned in fact let's do that really quick just call this text and equal to unsigned char signed text now the reason for this is just simply so that we don't get uh negative indexes into our lookup table because that would cause weird memory problems would definitely cause things to not work the way we want it to i'm also going to do like i did before i'm going to create a length variable and we're going to just grab the length of our text and that's going to help us down below now for those of you that saw the last video you're going to notice that search feels a lot like insert and that's because i mean insert in order to insert we were going through the try and actually trying to i mean in a way we were searching and then adding if the thing that we were trying to add wasn't already there so once again we're also going to need a temporary node and we're going to set it equal to root so this beginning looks just like insert and just like insert we're also going to use a for loop here same basic style of operation we know how long the string is that we're working with and so we're just going to run through it character by character also similarly we're going to have an if statement it says if the the temporary nodes children basically we're going to look at the symbol the i symbol in the string and if the child node at that point if it's null then at this point we know that it really isn't contained here so before we added nodes because we were actually trying to insert in this case we're searching so in this case it's not here and we can just return false anytime we see this okay and then of course as before we're going to do the same thing where we just set temp equal to the eighth child or the text ith child basically yeah so so in case you're wondering there's a lot going on here right um one way that i could have written this so i'm writing this all on one line but i could have said something like you know character c well it'd be unsigned character c equals texts of i so i'm basically grabbing the ith character and then just pass that in as the index that's basically the lookup table you pass in the character and it gives you the pointer to the child okay to keep my code concise i'm not going to do that i'm just going to let's go back to the way it was and we'll keep this just like this but anyway just in case i'm doing a lot on one line and that confuses anyone i want to just make clear what's going on okay now basically once we get to the end of this for loop if we haven't returned false meaning that we ran into a node that wasn't there at this point we know that we didn't return so there are enough nodes this child could be there now the only thing we need to do is check the terminal value and for this i can just return temp terminal and that's because if terminal is true then it is there so return true if temp terminal is false then that means that it's not there even though the node was there it hasn't been added so so we'll return false and that is all we need to do for our search try function this will actually search our try and it'll return true if the thing we're searching for is there and false if it's not but let's not make assumptions and take my word for it let's go down into main and let's actually test this out so really quick let's just put a few let's print off um search for cattle and let's print out the value that's going to be my boolean when it comes back and we'll just call search try root cattle now let's search for a few others let's search for cattle and we'll search for cat so we'll do one that actually is at the end it's kind of a leaf note of the tree and one that's in the middle and let's also search for kitten which is not there so so this one it should not be found okay so this should just give us a few different options a way for us to actually see whether search is working let's compile it and if we run it you can see yes it finds cattle it finds cat and it doesn't find kitten so things are working the way we expect okay so search seems to work now let's look into deleting words from the try this is probably the most complicated operation that we're going to look at it's not too bad but there are a few more things to keep straight so let's go up and see if we can create a delete function so again we're going to return bool from this delete function i'm going to call this delete key it's going to delete a string or let's let's call it delete string delete str um again we're going to take in a try node double pointer so again this is just like an insert because we may have to actually change the value of root and we're going to pass in once again a character pointer that we're going to call sign text okay again nothing too complicated that the whole reason is i want to pass in a standard character pointer but they can be signed and so that's annoying for this case so let's just change this again to text and assign character pointer okay and we're going to also have a result variable that we're going to start out as false meaning we didn't delete anything so again so we got this is gonna we're gonna return a result it's gonna be false if we didn't return something true if we did return something and i'm gonna implement this delete function as a recursive function as well it just makes some things a little bit easier there are other ways to do it so this is just one way this is the way i'm going to do it today but so i'm going to try to do this by creating another recursive function and this delete str function is simply going to be our wrapper around that function okay so my recursive function down here is going to take in a pointer so let's call this delete str rec recursive and we're going to pass in like we're going to pass in the root well we'll just pass in a single pointer in this case and we're going to pass in the text that we're trying to delete and we're also going to pass in a pointer to a boolean so that's the results we're going to pass in the address of the result and that's going to allow this recursive function to change the result and then i'm going to actually assign whatever this delete str rec returns that's going to be assigned to my root okay one other case that i'm going to handle up here as well is that if the root happens to be null from the beginning we can just return false we can save ourselves the time okay now you may wonder why i assigned root to here why i'm actually assigning a pointer and we're going to look at that just here in a minute i don't want to confuse you but this is a technique that allows me to pass in a single pointer into this recursive function but still be able to change the root value in case all the nodes below it get deleted and i just need to set root equal to null this will totally work so i hope this isn't too confusing i hope it makes sense as we start to build out our recursive function but this is just another way to allow the root node to change and hopefully that'll make plenty of sense up above as we finish up the code but then basically here i'm just going to return the result and you might be thinking where was that set well it's going to be set in my recursive function here so let's just copy this we'll come up here and actually start implementing this and this is going to be a try node call it root i'm actually going to call it node unsign character pointer text and this is going to be a boolean pointer called result okay and we're going to return a try node pointer okay and rather than result i'm going to change this to deleted just to make things a little more readable now down here we're going to say if the node equals null then return node okay so basically that's saying if if you passed in a null pointer into here then just return the node now we actually technically don't need this i don't think because we checked for right here but you know it doesn't hurt i'll just leave it in for now we could take it out later if we wanted it would make things slightly faster okay so now let's look at a second base case here which is that we've reached the end of a string so you've passed in a string that basically is empty what this is going to look like is you're going to say if text if the character the text points to happens to equal the null character then we know that we've reached the end of the string we've reached the end of the input string and the reason we got to this point is that each time i recurse i'm going to remove a single character from the front of the array and i'm going to show you how that's going to work in a second but when we reach this case where our text starts with the null character then we know we've reached the end so here what i'm going to do is just check to see if the node that i'm pointing to is actually terminal okay so if it is it means the string is actually in the try and we can delete it so if it is then what i'm going to want to do is i actually want to delete it so what i'm going to do is set the node's terminal value equal to false and then i'm going to set deleted equals true okay so again i'm passing in a pointer so that i can change this and it'll actually be reflected outside of the function and at this point if i don't care about space the node is deleted the node's basically gone if i search for it it won't be here but i do want to clean up nodes if i don't need them anymore and so what i'm going to do is i'm going to do right here just logically thinking through it right here i'm going to say let's say we have a function that is like node has children basically if the node that i'm looking at has no children so i just deleted something and it has no child nodes then i actually want to free this node and let's free it up and then i want to set that node equal to null okay now you say wait a minute setting that equal to null isn't going to have any effect because it's a single pointer whatever that's fine but what i'm going to do down here is just return node and so you remember that when we return basically we're turning a try node and that's going to replace the original node pointer so this is going to be just fine now we're done with our base cases now we need to do is just recurse okay so if we're not at the end of the string what we're going to do is say no children again we're going to pass in the symbol or the first character before we did i character but this is the first one that's fine i'm going to copy this really quick and then we're going to just recursively call our delete string rec and we're gonna pass in this node so we're gonna pass in the child node and then we're gonna return one character we're gonna do it like this just by adding one to the pointer and then we're also going to pass in the deleted variable this pointer just so that they can update on a recursive call whether it's been deleted or not now this little point of arithmetic that i did here might confuse some of you i could just as easily have made a copy of the text and copied all but the first character but instead since i'm not actually changing the text at all in these recursive calls i'm just moving the pointer over one and so that next recursion step will have the same text but it's gonna start one character further over so this is going to be faster it's just going to look to that recursive call like there's one last character and it's going to save me a lot of time by not making a bunch of copies and it's also going to produce less code so i like this approach but i totally recognize that it might be a little less readable than you're used to but i hope it helps you see another way that you can manage strings in the future now this recursive call again is going to return a pointer that pointer is going to be the new value that this child node needs to point to so that's why i'm just assigning it to itself right here okay now at this point we are almost done with delete now the last thing i need to do is check to see if we need to delete any intermediate nodes okay right because we might delete a node and then as we recurse back up the tree we may have a bunch of other nodes we need to delete and so here we're just going to check to see so if deleted and let's say node has children equals false so we always have to check this we always have to check to see if we have a node that doesn't have children if it has if it has child nodes we just want to leave it be but if it doesn't have child nodes then that means we can probably clean up something and we also have to make sure that this node is not terminal and then down here so if this happens if we have deleted a node so we're cursing back up the tree so if we've deleted a node in a recursive call and that and the current node has no children and the current node is not terminal then we can free this node and basically just reclaim some memory so we're going to free this node basically do the same thing we did up above and node equals null and then here we're going to return our node so now we're closer to done we just have one little issue and that is this node has children function that i keep calling but it doesn't actually exist yet so let's go up and just implement that really quick um it's going to return a boolean node has children and we're going to pass in a tri-node pointer and then of course if the node is null then we'll just return false because there's nothing here to see but otherwise let's just check to see if it has children so we'll go and i equals 0 to numcare so we're just going to go through each of the elements in this array and if any of these children so let's say if no children i is not equal to null then we know there's at least one child and so there's at least one child so we can return true it does in fact have children and otherwise when we get done with the whole loop if we haven't found anything then we can return false and note that this is one of the slower operations in our try here and this is why in the delete operation down here this is why you notice that i'm checking deleted i didn't really have to do this but it allows me to avoid extra calls to this node has children function because that's kind of expensive and i'd like to avoid that so checking the deleted first basically if this turns out to be that we didn't delete anything it's not going to bother checking the rest of these and so that's going to speed things up a bit and there are some other optimizations you could do to speed up deletions a bit but for today but for today i think this will be okay so now let's jump down to main and see make sure that everything actually works so let's come down here and delete some strings and we'll pass in the address of root and let's remove kin and let's remove cat and then i'm just going to print out my try again and let's just make sure that it actually works and now if we come down we can pilot and we run it it seems to work so naturally we would want to do a little more testing to guarantee that i haven't messed anything up there's a lot going on in that delete function and if you think i did make a mistake which is actually completely possible let me know down in the comments but i hope this is helpful it rounds out our try example like this video if you found it useful subscribe if you want to take our relationship to the next level and not miss my next videos and until the next one i'll see you later

Channel: Jacob Sorber

Views: 9,123

Keywords:

Id: NDfAYZCHstI

Length: 16min 45sec (1005 seconds)

Published: Tue May 25 2021