Data Structures in Golang - The trie data structure

hello today we'll be talking about a data structure called price you will learn what tries are and also learn about how they specifically work uh like always i'll be explaining basic concepts first with diagrams and stuff and then after that we will go and do some coding okay so let's dive in um a try is a tree structure which is mostly used for storing words each node will represent a word or part of a word and by connecting the path from the root to that node we can store words in this particular structure we do this because it lets us search words pretty fast uh one application for tries is autocomplete uh you know how like when you're like searching something in google and as we type in like a search word in the search bar google tries to guess what we're trying to type and the more letters we type in the more closer it gets is and tries can also use this to suggest what the next word would be uh look at this try over here the tri is currently holding the words aragorn aragog aragon eragon oregon oregano and oreo tries will have a root node at the top which will have children nodes one for each possible alphabet there are 26 letters in the alphabet so each node will have 26 children nodes just to keep it simple in this diagram i didn't draw all the like empty nodes but if you actually look into each node it will have an array where each index will represent all the possible characters in the alphabet and the ones that represent the children will have a pointer inside it that points to that child node for example let's look into this node that holds the r in aragorn and aragog this node will have an array with a size of 26. and the indices will be all nil except for the ones that represent a and g each node needs to hold this array containing the addresses of the next notes but it also needs needs another piece of information the nodes need to have a boolean value indicating whether the node is an end of a word or not for example in the word oreo o r e will have false as a value for the is end value but the last node of oreo with the letter o will have true as the value indicating that that is the last letter of the word uh if we set the is and value of the r node in oreo we would be adding the word or in the list and or would be stored in the try along with the others now that we know the basic structure of tries let's see how we can insert and search words inside a try let's say we want to add a new word orc first we start at the root and look into the array that holds the address of the children then we'll see if there is something in the index that represents the first letter of orc which is o so yes it has it there is a pointer at that index that points to the child node for o so let's go to that node this is also a node just like the other nodes like the root nodes or any other node so it will also have an array that holds the pointers of the children and this time we'll see if there is something in r because that's the second letter in org and yes there is so which means we have a node for that same goes for the next node we'll see if there is something in the index for c which is the third letter of auric so this is where we create a new node and add the address of the new node to the array index of c but this is not the end because we finished adding the word org we need to set the is n value of the last node as true okay so that's the end of inserting a word now that we successfully added the new word orc let's go and try to search this word in the try the process is similar to inserting the node go to the root and just check if there is a match for the first letter then follow that pointer to get to the next node and check for the second letter r which is there and then to the next to search for the third letter c which is also there so we have o r and c in the try but there is one more last step we need to check if the is n value of the last character c is true if we try to search for a word that is not in the list for example orb it will immediately let us know that the word is not there once it finds an empty index of the children array now let's talk a bit about the time complexity of a try the big o will indicate how fast and efficiently inserting or searching in a try can be let's say the length of the keyword we're searching or inserting is is m in that case the time complexity will be om because we will have to follow down the tree m times however this is not always the case there can be a better scenario when we are searching the try if the search meets an empty spot for the next character it would immediately stop the search and return false so in that case it would be better than om if we use tries we can search words very fast but usually a try can take a lot of space think about each node has 26 children and the required space will exponentially grow as we add longer and longer words in into the try this is why tries are known to have a trade-off between time and space okay so so far we looked into what tries are and how they worked and now let's go and try to implement that in code okay so uh let's start coding um just the basics we're basically going to do three things here uh the first one is to make the structure for the node and the tries the second is to make an insert method and the third is to make a search method so let's just write that down here we first need to make a struct for a node and a struct for a try and also an insert method and a search method okay these are the three things um making the structure for the node and try um insert and search we are going to do these three things so let's start with node so like i explained before the node first needs to hold an array and the array is going to be a size of 26 which is the size of the alphabet and each index of that array is going to hold a pointer pointing to the child so uh it's gonna we can call it children and it's going to be size of 26 and it's going to be a pointer pointing to another node but uh one thing about this is it's not a good idea to actually hard code the numbers inside here so i'm going to make that into a const a constant and i will call it alphabet size and that is going to be 26. because this is starting with a capital i'm that means that i'm going to use it somewhere else so it's a good idea to actually just make a comment on explaining what it is okay and before i explain that the try the node needs another piece of information which is indicating whether the node is an end of a word or not so i'm going to make another variable and that's going to be a boolean value okay so that is the structure of a of a node this time i'm going to make a structure of a try and the try is going to be very simple it's just going to hold a pointer pointing to the root node of that try we will call it a root and that's just going to be a pointer pointing to the root node okay so when i want to try to initiate a try i will first have to create this struct and then i'll have to create a node the first node that will become the root and then make a node with this and then appoint that to this try so i'm just going to make a function that can actually do that process i will call it init try in it try and there is no parameters but it's going to return a pointer pointing to that uh try that is created so the return should be a pointer of a try and here i'm just going to go result and first we need to create a try and inside that try we're going to appoint a root and we're going to create a node that is going to become the root okay so right now what we're doing is oh right now what we're doing is we're going to create this node put that pointer as the root as we create a try and it's going to return the results here so return result okay and we need to put a comment here in it try i will create a new fight we made we just made the structure we have a structure of a node and a try and a function that can initiate a try okay so let's go and see if it works i'm just going to make a very simple um test try and i'm going to init okay so this is going to initiate a try and i'm going to name that test try and i will just kind of print it out print out the whole thing okay so right now this is going to be the address of the the try that is created uh we don't have that much information here we don't like like we can't check if the node is created properly so i'm just gonna say test try dot root to check if we have an empty node inside there i want to check if it if it's um creating it properly oh so yes uh this is going to be what's inside the node the root node and right now you can see everything is set to default all the values in the array is nil and false value for the is end okay nice all right so the next step we're going to do the insert method okay so insert is going to take in a word which is going to be w inside the function and it's going to add it to the try so we're just going to implement what i explained before with the diagrams we're just going to do the exactly the same thing the first step is to loop through this loop through w which is the word i'm trying to add loop through the characters if i'm going to add the word orc i'll have to try to elute through o r and c and see if there's a match and if there is no match i'm going to add a node create a node and add it to that character so first i'm going to build a structure inside this method so that i can make a loop so it's going to be 4 i starting from 0 2 i smaller than the length of w and i plus plus okay actually i want to put this as a variable i'm going to call it word length and i'm going to go okay so we're going to travel from the root and compare it to the first letter of org and move to the next node and compare it to the second letter of auric we have to do that process so we want to indicate we want to have a variable that can indicate where the current node is the one that we're at so i'm going to express that as current node and right now we have to start at the root so that's going to be t dot root if the current node and because it's a node it's going to have children and inside here we need to put the index of the character of that children so in that case we need to change the characters into the index if we're going to do insert orc then this is going to be o but we want to change it into the index and we express that as this so just to give you a better understanding of what's going on here i'm going to bring this in i'm going to print out that and if you run it you'll see that it's indicating 97. so for example what i want is i want a to become zero because it's the first letter of the alphabet i want a to become zero i want b to become one c to become two so in that case what i need to do is so whatever i put in here uh the char index is going to become this number over here if i want to put o then the index number 14 of the children array will represent the letter o so that is why it's going to look like this right now i'm trying to change uh this character into the character index of the children array so that's why i'm going to go like that so as we follow along from orc we're trying to find where there is no match there is nothing there is an empty index representing the character so we can express that as nil and if it actually becomes nil we're going to create a node and put it into that empty space create a node get the pointer and put it into that index so we can say current no dot children so this is where it's nil in that nil place in that nil index i am going to assign the pointer of a new node so i just created a node and put it in there so in that case that created node is going to become a child of that current node and for this for loop to work after we finished each loop uh we need to update it right let's say um there was a match and this if statement was all ignored in that case we need a line that can actually let the node go to the next so in that case you need to update the current node okay so if that index is not empty we're going to follow that index and we're going to put that into the current node which is going to be the next node okay this is not the end after we added the last node we have to indicate that that's the the end of the word so uh and this has to come at the the end of the insert method okay so now we're going to do a search method a search method is going to take in a word and return true if that word is included in the try so yes this means that this function is going to be a method of the structure try and it's going to be called search it's going to take in a word and it's going to return a boolean value okay the searching process is very similar to the inserting when we don't find a match instead of creating a new node and inserting it we're just going to return false so i think it's um code wise it's easier than an insert so i'm just going to copy and paste all the stuff that i wrote here and put it here and fix it a little bit so i guess these parts you we already went over it so i don't have to explain that to you again but here instead of creating a new node and putting it into the current node i am going to just return false we just immediately know that that word is not in this try so we just immediately return false we still need to update the for loop so i'm going to leave this part and this part over here needs to be turned into an if statement saying that if it's true then yes we're going to return a true current node.isen is true then we will return true so the condition of returning true is first it needs to successfully pass this for loop without returning a false which means it needs to have match for each node and then it's able to return true when the last node the is end value is true of the last node so right now the current node here is going to be the last node because we kept on updating it with this line over here okay and at the end we're just going to return false in case the is end is not true even if we have like all the matches in the for loop but this didn't come through in that case it's not the end of the word so we're going to return a false okay i forgot to put two equals there so now we have the search method and the insert method let's go and write something in here so that we can test it out so we have test trial let's just change the word uh change the um and instead of that okay so i'm just inserting one word aragorn and searching it so this one should actually return a true which i'm going to print out all right okay oh true we got a true so right now we inserted aragorn and then we uh searched it and it turns out that it is there um like like the video before instead of actually like going like that i'm just going to make it a bit more simple and use a for loop let's call it to add that's going to be my slice okay so right now i made a slice and named it to add and put all the words i want to add to the try and then i made a full loop so it can insert all these words after that i'm going to try to search one of the words here which let's search aragon and let's say if let's see if that returns a true okay okay so yes it returns a true um let's try to add something that's not there wizard okay so false it's not there i hope you know more about price now and if this video was helpful and you want to see more of my videos uh please subscribe to this channel and thank you so much for watching and have a good day i'll see you in the next video

Channel: Junmin Lee

Views: 9,341

Keywords: data structures, golang, leetcode, coding, programming, coding tutorial, programming tutorial, algorithms, computer science, software development, binary search tree, go, tries, trie, tries in go, tries in golang, hackerrank, golang tutorial, golang tutorial for beginners

Id: nL7BHR5vJDc

Length: 22min 45sec (1365 seconds)

Published: Sun Aug 16 2020