Tries

Resources

1. Trie Overview
2. Trie Overview + Implementation
3. Trie Operations + Implementations
4. In Depth Trie Explanation
5. A good implementation of the delete operation

(Also worth mentioning is this article from the Visual Studio Magazine. The article explains tries and why you might want to use them.)

Takeaways:

• A trie is an ordered tree that compactly stores strings. Each node in a trie represents a single character in a string. Say we store the words "car" and "cars" in a trie - the trie would only use four nodes for both - one for each distinct letter of the words (c,a,r,s).
• They are also known as digital trees and prefix trees.
• A trie is most efficient when it is storing strings with similar prefixes, but in general tries are usually not space efficient. They have a space complexity of O(n + k).
• They are useful for queries involving string prefixes, such as suggesting the next character(s) for a given prefix.
• Tries are not usually found in standard libraries of popular languages (Java & C#, for example, do not have a trie data structure).
• Tries are typically implemented using arrays or hash tables.
• Although hash table implementations are more flexible, array implementations can be more efficient by placing limitations on the trie (like only allowing characters a-z)
• Many trie implementations will use booleans to mark the end of words/strings. But some implementations will use an additional node appended after the last character of the word. This additional node might contain a NULL value or a special character.
• Similarly, the root/head node of a trie can be represented in various ways. For my implementations I used a special character ($) to denote the root node.
• Inserting and searching are both O(k) operations.
• A related data structure is a radix tree
• Radix trees are basically a space efficient trie. A trie only stores one character per node, whereas a radix tree can store many. A radix tree is essentially a trie where all nodes that are the only child are merged with their parent nodes - this means less total nodes are required for the same number of words.

Below you will find two trie implementations:

As always, if you found any errors in this post please let me know!