Trie - Data Structures in Python #7

Key Takeaways

what is going on guys welcome back to the python data structures tutorial Series in this video today we're going to implement the TR data structure so let us get right into it not a g it's AED all right so we're going to implement the TR data structure from scratch in Python today and as always I want to start by giving you guys a brief explanation of the data structure and Theory here before we get into the coding and as a side note for those of you who are interested in that the data structure name is written like this t r i e and it actually comes from the word retrieval which means that the original correct pronunciation would be tree now why do we call it try mainly to distinguish it from the concept of a tree especially because the try is also a tree it's a tree data structure which means that if you just say oh we're working with a tree we don't really know what we're talking about uh if I say I'm working with a tree data structure so we're call calling it try mainly to distinguish it from the tree to know it's not just a tree it's a try that's the only reason why we pronounce it that way actually it would be pronounced tree because it comes from the word retrieval just as a side note here for those of you interested in that um but let's take a look at the data structure itself what's the idea behind it it's a tree as we said and it's very useful for working with strings and primarily used for things like uh autoc completion or having a dictionary for example um and and the idea is the following we have a root note and every note has two things a dictionary of children or of child notes and uh a flag saying if this is the end of a word yes or no so we're going to say that if a note is the end of a word we're going to write end in it otherwise I'm going to leave it empty so this is the root note now it is not the end of a word and our try is empty now let's say I want to insert a word for example hello how would I do this now what happens here is I go letter by letter and I insert the word into this TR data structure so right now the root node doesn't have any child elements so what I do is I'm looking for H H doesn't exist so I'm going to create a new key value pair where H is the key and H points to a note and this note now has again its own dictionary and can be the end of a word or not now it's not the end of a word so we're going to continue next up we have e e is not part of this note or of this dictionary so we're going to add it E points to the next note which again has a dictionary here we're going to do the same thing L points to the next note has a dictionary with another L points to the next note um and this one has a dictionary with O and then this o points to a note which has an empty dictionary and is the end of a word word this is how we would insert hello into our try so we have the root note with the dictionary the H points to a note that has an e pointing to a note that has an L pointing to a Noe that has an L pointing to a note that has an o pointing to a note that right now is empty and has end uh the nend flex set to true now we can also import or insert another word for example minimum like this minimum um and we could see what happens here now there's a reason I choose this word I'm going to show this here in a second but let's say now I'm not going to use the dictionary notation here I'm just going to use connections but it's the same idea the m is pointing to a note which is pointing to uh which has I pointing to another note n i m u M and N so why am I using this word because there are a couple of words that are quite similar and we're going to see what happens for example if I now insert the word minimal like this minimal um what happens in this case is if I want to insert this word I go m i n i m and then I see that here in this dictionary this this note here has the dictionary U that points to this note and and what I do now is I add another key value pair so I say a which points now to another note I'm going to do it like this so I'm going to just say we have another Branch here a which goes to another node which goes using L to another node which is also the end of a word and now you can see they have the same prefix by the way this data structure here is not just called try it's also called a prefix tree this is also a way to to refer to this data structure a prefix tree and the reason for that is you can see m i n i m minim is the prefix for minimal and for minimum which can be useful again for autocompletion now another thing that we can do is let's say I want to insert the word mini what happens in this case well in this case all I have to do is I have to go m i n i and then I have to set this to n now n doesn't prevent my try from going further so I can still go to minimal but it says that this is the end of a word it doesn't have to be the end of the search but it is the end of one word so many is actually a word and this can be useful now because if now I ask okay give me an autoc completion for Mi I can efficiently find mini minimal and minimum and I can extend this I can build a dictionary like this I can have have uh certain keywords like this this is a very useful data structure and this is what we're going to implement in Python from scratch today so let us get started I'm going to or I'm already in my current directory I'm going to delete everything that's in here actually we don't have anything in here so I'm going to create a new file I'm going to call it try. py and we're going to have of course a note class so class node is going to have a Constructor and it's going to have self. children set to an empty dictionary um and self dot or actually I'm not sure if this is an empty dictionary or a set so let's actually let's actually say dict like this um and then we're going to say end of word or actually let's call this is end of word is equal to false by default that is our note that's about it and then we're going to have a class try and this try is going to have an init method and in this init method we're going to initialize the root note so we're going to say self. root is equal to note all right so every tree is going to start with a root note that has an empty child dictionary and is not the end of a word by default now let's define again what kind of methods we're going to implement for this data structure we're going to have an insert method which is going to allow us to insert a word into the try we're going to have a search method which is going to tell us if a given word is part of the try so for example in our tree here if I type Min I'm going to get true if I try uh if I type uh minimalistic I'm not going to get a true I'm going to get a false that's the basic idea here then we also want to have a delete method so that I can remove words how would I do that in theory of course I would just remove the end flag if I remove mini for example so if I remove mini I would just set this to false again um if I remove something else I also delete the notes and the connections uh we're going to take a look at that uh when we get to the implementation then we also want to have has prefix the basic idea here is that we check if the prefix is part of the tree or not and then we also want to have two a little bit more not necessarily complicated but they're going to take more R they're going to have a higher runtime complexity if that's the correct term higher um but they're going to be a little bit more difficult which are going to be the uh starts with method so for this method we're going to pass a prefix and this prefix or this this method will give us all the words that start with this prefix so it's going to search the tree um and then we're going to also have list words which is basically going to give us all the words of the dictionary you could say so we don't need a prefix for this we just get all the words and that's basically it that is going to be our Tri data structure now let us start with the insertion we already talked about this how do we insert we start at the root node we say current node is equal to root and then what we do is we say for character in our word so we go character by character we say if the character is not part of the dictionary of the current notes so if we don't find the character as a key in the children dictionary of the current note what we do is we say uh current node. children add this new uh add this character as a key and let it point to a new note that we create um and whether we had to create it or not afterwards we're just going to say that the current note is going to be that note so current note. C so either it was there before then we're just going there and otherwise we're creating it and then going there and we do that until we have no characters left in our word and then what we do is we say current noes do is end of word equals to true it's as simple as that we just follow the path until we get there or we have to create new notes until we get there until the word is processed and at the end at the note that we're currently at we're going to just set end of word to true this can be an already existing node like it was the case for Mini in this case we just set it or it was the note we just created in this case we also just set it uh so the insertion is quite simple we're going to talk about the rantom complexities later on this search is also quite simple because we have to do basically the same thing but instead of creating it if we don't find it we return false so we say current node is equal to self. root and then we say for character in wart if the character is um not in the current node children we're going to return false because we obviously don't have it so if I get to a point where I have a character and it's not part of the children dictionary of my current node it means the word does not exist obviously because the next character does not exist so I'm going to return false in this case otherwise I'm going to keep going down the line so I'm going to say current node children C move further and in the end we're going to say uh once the word is processed we want to know the the word or the note I'm currently at is it the end of a word or not so I'm going to return current node is end of word because of course I can find the term for example here what I I could find is uh mini mum without the m so mini ma uh like here I could end up here which would be a valid note but I would not have it set to end which means that I would get uh false here as a return so that's that now the rest is going to be a little bit more um or actually has prefix is kind of simple so for has prefix we can also do the same thing actually I think we can just copy this actually now I copied it to my diction uh to my to my clipboard so let's go paste it down here uh the only difference here is that we're going to return true every time so it doesn't need to be the end of the word because we're not checking if the word exists we're checking if the prefix exists so if I end up at a note I can return true now the deletion will be a little bit more complicated um because we need to define a helper function underscore delete we're going to say deore delete and this function will get parameters so that we can keep track of certain things first of all it will get the current note it will get the word and it will get the index so that we can recursively call it and update the progress so to say um the idea is I'm going to call this function or this method in delete once initially so self- delete on the root note so I'm going to say self. root this is the word that needs to be deleted and I'm currently at index zero so we haven't processed anything of the word yet and in our delete method this is going to be a recursive method so it's going to call itself we're going to have um first of all some base cases for terminating we're going to say if the index is equal to the length of the word then we're done and I basically just have to see is this um the end of a word so if not if this is not the current node is not the end of the word we return false why do we return false because we don't need to do anything we don't need to delete anything this happens when the word didn't exist anyway so we don't need to delete anything uh on the upper levels we can just say okay if I'm ending up at a place that is not a word I don't even have to do anything so return false uh the return value is important because we have to also recursively remove notes if um if it's necessary so basically if I'm removing this here I just need to set it to not end of a word anymore so if I'm removing many if I'm removing minimal I have to remove this I have to remove this and also this connection here so I have to remove more than just uh setting this to not being an end anymore unless I want to keep like this or not not even unless I want to keep the structure I have to delete it because otherwise minimal would be a valid prefix which it shouldn't be so this is why I use the return values here so if I end up at a place that is not the word I just return false because obviously I'm not removing anything here um and then I'm going to say current note in all cases current note is end of word is going to be equal to false now if it was false already this doesn't change anything if it was true it means that I'm ending up at a place where this is a word this is the end of a word and it is set to true so I'm going to set it to false now to say this is no longer a word I'm removing it from the dictionary so to say from the try um and then I want to return Here length of current node. children is equal to zero if that is the case I want to return true so if if I don't have any child notes at a current note I can return true because that means that I can delete um other notes as well whereas if this has child noes I cannot just delete everything because there are other words that would be impacted by it so I return true which means you can delete the note um if this note doesn't contain any child noes um so that's the base case otherwise what we're going to do or not just otherwise or actually otherwise yeah because uh we return if we get to the if statement uh otherwise what we're going to do is we're going to say the character is the word at the specific index remember we're passing the index here uh we're going to pass the index here recursively uh when we call the delete method but by default or in the beginning it's zero so we're getting the first character um or the character at the index and then we say node is equal to current node children get C so from the current note I'm looking at the child dictionary I'm getting the note um that corresponds to the Key C now there is the case that this note does not exist so if or this key does not exist if this is the case this is going to return none and I can return false because the word doesn't exist if the word does exist uh what I do is I delete the current Noe how do I do that or I I don't delete the current Noe I call recursively the delete function but I have to store whether I have to delete a current note or not in a variable so this is why we need to return value so we say delete current note you could imagine a question mark here is equal to self doore delete calling it on this next note with the same word and the index increased by one so what this means is we go one node forward and we also increase the index by one so that we can continue the same process down the line and this is going to recursively return true or false and if it returns true it means that I can delete the current node if it returns false it means that I'm not going to delete the current node so at some point this is going to return finally and then I want to know if delete current node what I'm going to do is I'm going to delete current note children C and I'm going to return also here uh for this note if the length of um of the current note. children is equal to zero and also the current node is not end of the word so basically I get the instruction delete this note and then I delete this note from from the children and I also say for this note deleted if it has no children or if and if it's not the end of a word so that we can recursively delete all the notes that are no longer necessary in our try I hope this was not too confusing in the explanation the basic idea here visually again let me show this is for some notes when you when you want to delete the word like mini all you have to do is you have to delete the flag that it's the end of a word you don't have to remove any other references here because it has child notes but for example if I remove minimal this doesn't have child notes so I can remove this note I can remove of course the Flack I can remove that this is the end of a word but I also don't have children which means I can remove this note which means I can remove this note because it then also doesn't have any children anymore uh which means that um this connection can also be removed but then of course this should not be removed because it does have children it does have minimum uh another word that is also part of our try so I hope this is somewhat easy to understand here why we're doing it that way even though the recursion might be confusing but we're basically returning should you delete me or should you not delete me that's the return value all right so that's the delete method and now for the start with and for the list words method we're going to use a depth first search so a DFS algorithm the basic idea is you want to go to a certain prefix and then you want to get all the child words so not just the notes but the words you want to explore all the child notes to find words and you want to collect them in a list so we're going to say words is equal to an empty list and we start again at the root note then we say for C in prefix so we want to go to the position um and we want to say if c not in um current node. children we're going to return an empty list or actually we can return words because it's going to be an empty list at this point um but if we don't get into this if statement we're going to just go further and further we're going to say current node is equal to current node children C which means we're going to go to the prefix for example if my prefix is m or if my prefix is Mini or let's say Min I would go to this point here Min this is where I'm at now and from here I can start a DFS so I can go like this and then like this so a depth first search um all right so once this is done we're going to be at the position of the last prefix character and then we're going to Define here a helper method which is going to be in it's going to be a nested method inside of this uh starts with method and I'm going to saycore DFS is going to get a current note and a path the path is important to be able to reconstruct the word and this is going to recursively call itself so we have quite a bit of recursion today uh basically the idea is if the current note is the end of a word we want to store it we want to add it to our words uh list here so if we end up at a note that is the end of a word what we want to do is we want to say append to the words list um the path and the path is going to be a collection of characters um so in order to get it as a word we need to join it so we're going to say join uh not word sorry path um so the path is going to be what we recursively pass here to the function call so if we are at the end of the word get all the characters join them together and append them to the words list uh and then we're going to say fore child noes in current node children items so basically for the key and child node C being the character that performs the transition child node being the note that the transition is performed to uh we're going to say DFS go to that child node and say path plus and then list C this is important that it's a list because we're extending an existing list so this is the list of characters that we have we collect all the characters and at the moment we arrive or the moment we arrive at um at the end of a word we collect it and of course we need to call this method once we need to say DFS current note here and we start with a prefix this is important because you want to not start with an empty list you already have the beginning for example Min is already part of the word so you want to append to it um in our example I can show you that uh what we want to do here is we want to go to this position to Min and then what we want to do is we want to do the DFS so we want to go down oh here's the end of a word so what I do is I have now m i n e uh m i n i and I want to join them together to mini and collect them in my list of word then I go deeper I say m then I say a l o end of word perfect so I can say now um I have M A join them together minimal and then I also have here a second call of course u m o end of the word okay this is minimum so I found all the words that have this prefix that start with Min um and of course what I need to do in the end is I need to return the list of words all right Now list words is basically a similar approach only difference being we don't need a prefix so what we do here is we say words is equal to an empty list and we say again DFS we're going to have a current Noe and a path actually I think this is the exact same implementation so I'm going to just copy this and we're going to say that um the only difference is that we're calling this D DFS now on self. root with an empty list as the prefix and then we say return words that's it now if I didn't make any mistakes which would be surprising as always um that is the try data structure so I'm going to write some uh test cases here just to see if this works and then we're going to talk about the runtime complexity so if name is equal to main what I want to do is I want create a try and actually let me think about this I'm going to just copy paste what I have here in my prepared code so that we don't have to actually this was not the correct key let me just do it like this this there you go and uh what we do here is We have basically a try we insert hello Henry Mike minimal minimum let's also insert many and and um then we have or actually I'm inserting mini down here so let's remove it here uh let's run this code to see if it works no it doesn't work key error H perfect this means that our insert method probably doesn't work correctly so what's the problem here oh I found the problem it's that we're missing a knot here of course you want to create a new note if it's not in the children you otherwise want to just go to the note but if you don't have the character already in the list then you want to create a new one otherwise just jump to the existing one that's a problem um we have another problem which is name wart is not defined so where is that again this is in has prefix oh is this because we're lacking a parameter no actually has prefix is fine but we need to say prefix and now it should work okay let's compare the code or let's compare what it should do we insert hello Henry Mike minimal minimum we can print that we get it um this is from list word so this works then we say has prefix actually what we're asking for here is MI it has it um if I say start with Mi I get mic minimal minimum if I say um delete minimal and then I do starts with Mi again I get Mike and minimum then I search for certain words I search for minimum minimal and mini I get uh in this case true false false because I removed minimum and then we insert uh or I removed minimal uh then we insert mini and then I say starts with Mi I and I'm getting Mike mini and minimum so as you can see this works and now let's talk about the runtime complexity how difficult is it to do that well for the insert we have o of M so linear runtime complexity where m is the length of the key so actually the length of the word we could say so depending on how long the word is it we're inserting that's what determines the rtime complexity doesn't matter how large a tree is it doesn't matter um you know how many words are already in there it matters how long the new word is that I'm trying to insert o of M where m is the length of the word so it's linear in terms of word length um when it comes to the search it is basically the same o m o of M actually let me just copy that because what do we need to do we need to just go and look up the characters and go to the next node and next node and next node now of course we can terminate earlier if we see that the first letter is already not part of the try then we can of course just terminate but in the worst case we have o of M which is the length of the word itself so then the same is also true for deletion o of M in this case actually I wanted to paste this here again um and for has prefix we also have o of M but for the other one uh for the starts with and for list words we have different rundown complexities for starts with we have the following we have O M plus K where m is the prefix length and K is the total number of characters in all suffixes basic idea be being I definitely have to go M because I have to go to the note where the prefix ends so that's for sure and then I have to go to all the characters um in all the suffixes so for example in our tree in our try here we definitely have to go to Min but then I also have to go to i m a l m u m now the thing is if they overlap I can save certain things so for example if my prefix is M then i n i and m overlap so I only have to count them once so I don't actually have to count uh all the word lengths because then I would have i n i which would be three I would have i n i m a l which would be all of that and then I would add all these together if I have overlaps this results in much less characters that I have to count because if they only differ in the last couple of characters and I have huge words that's going to make a difference but in the worst case I have um o of M plus K where m is the prefix length that's how far I have to go for sure and then K depends on the overlaps but K would be the total number of characters in all suffixes um and then we have also list words which is easy to to denote it's just o of n but n is the number of notes in the try we have to go through every single note uh in order to list all the words so depending on how many notes you have in the try that's how many notes you have to Traverse in order to list all the words so yeah this is how you implement the TR data structure in Python from scratch so that's it for today's video I hope you enjoyed it and hope you learned something if so let me know by hitting a like button and leaving a comment in the comment section down below and of course don't forget to subscribe to this Channel and hit the notification Bell to not miss a single future video for free other than that thank you much for watching see you in the next video and bye for