CS Level Up Series (30 Part Series)
- Trie Overview
- Trie Overview + Implementation
- Trie Operations + Implementations
- In Depth Trie Explanation
- 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.)
- 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
NULLvalue 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
- 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!