In this weeks article I'm going to be discussing Tries. A Trie is a data structure thats main purpose is retrieval. Tries are most often used to store and retrieve strings in O(L) time, where L is the length of the string. A common use of a Trie data structure is to do prefix searching, such as an autocomplete form.
As you can see in the example above, each node contains a letter. Each chain of nodes will result in a string. In theory we could use a trie to store every word in the dictionary, but that would use an incredible amount of memory. For this reason Tries are often replaced by other data structures when a prefix search isn't necessary.
Tries have two main functions:
- Insert
- Search
But before we dive into those, let's first start with implementing the overall structure.
We need to create two classes, a node class and our tree class. Each node will contain a value, which is the letter it represents, a boolean representing if it's the last letter in a word, and an object for holding the nodes children. The Trie will only need the root, which is initialized as an empty node.
For our insert method we need to traverse through our tree. So to start we initialize a node variable representing the node we are currently on, and set it to the root. For each character in the passed in word, we see if our current node is holding the character as a child, if it isn't we add it as a child. We then change our current node to that character and repeat until we've gone through the word. After our traversal we set the last node's status to show it is the last character of a word.
Our search method is similar to our insert method in that we are doing another traversal. However, all we do in the loop is check if each letter is present in the word. If all of the characters are there and the last character's status shows it's the last character of a word then we return true, otherwise we return false.
Thanks for reading! You can find the code for this post here.
Top comments (2)
This code is very confused. You define a
Nodeclass and only use it once. Further code reverts to using plain objects. You might want to revise this example to either use theNodeclass throughout (and itsdata,childrenproperties etc.), or just use plain objects throughout (remove theNodeclass, and make root{}).You've also stated that:
But you haven't shown an example of how that can be done! (Hint: the original
Nodeclass might be useful for this, if fully integrated)Other issues:
searchfunction returnsnullortrueinstead oftrue/falseas statednode !== nullpart of the return expression is entirely redundant, since it is alwaystruenode.isEndOfWord(although this would still be returningnull/true- but this isn't a big issue as JS has the concept of truthiness and falsiness)UPDATE: On further inspection, it's more luck than judgement that the
searchmethod even works - especially where you are checking for=== null- you won't find anullanywhere. Overall, your code will be finding a lot ofundefineds everywhere