A Crash Course in Tries
Trie, Trie, Trie again!
Audience
This article is aimed at developers with a working knowledge of trees (you can swot up on my article here). It gives a quick overview of tries and their applications, then concludes with a worked example of a tries-orientated problem.
Argument
Tries are a type of tree data structure, it contains nodes, edges, a root, and parent-child relationships. However, a trie acts as a key-value data store. The key is always a string, but the value can be anything. In fact, the value can be nothing at all! Tries can also be used to store a unique list of keys.
Let’s explore this concept with an example.
In the above diagram we have a trie for storing dictionaries of last names to first names. We can see it contains a single last name (Smith), and a single first name (John). Let’s add another two people, Jane Smith and Agon Smakaj.
We share the first two letters of the key, and from there branch out. It’s reasonably easy to see how this can be expanded into other applications.
One common use of this pattern is for primary keys in data stores. Additionally we may use it to search values by a prefix. If we were looking for names of people with last name beginning ‘Sm’, we could use this structure to retrieve all three of our entries. Often as tries expand we will limit these retrievals to a set number, say the first m
.
Hybrid Tries
From the previous diagrams we may notice that this structure is most useful when our keys share a lot of common letters. If this is not the case then our tree becomes too spread out and stops being helpful.
To circumvent this issue we may use a hybrid structure.
We set a threshold for our tree, and continue adding strings to a node until we reach this threshold. At this point we expand the node to a more traditional tree structure and carry on as before.
Employing Tries
This problem is taken from LeetCode and is formulated as follows
In English, we have a concept called root, which can be followed by some other word to form another longer word — let’s call this word successor. For example, when the root
"an"
is followed by the successor word"other"
, we can form a new word"another"
.Given a
dictionary
consisting of many roots and asentence
consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.Return the
sentence
after the replacement.
Imagine we are provided a dictionary of words: bat, cat and rat. We can expand this into a trie below (forgive the double use of root).
To find the shortest root of a successor we recurse down the tree, matching up letters until we reach the end of a branch. This is our root. If there is no match for a starting letter then there exists no root (fat, for example, would not match anything).
We have a solution below
Conclusion
In conclusion, we have covered tries, their properties and concluded with a worked example.