CS Level Up Series (28 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 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 some common bit manipulation
As always, if you found any errors in this post please let me know!
A social network 100% devoted to making you a better coder?
Level up every day