Trie
A trie is a rooted tree that maintains a set of strings. Each string in the set is stored as a chain of characters that starts at the root. If two strings have a common prefix, they also have a common chain in the tree.
https://leetcode.com/problems/implement-trie-prefix-tree/submissions/
First learned in CS240.
A Trie is a dictionary for bitstrings. Make sure you are familiar with the String Algorithms terminology
- Comes from retrieval, but pronounced “try”
- A tree based on bitwise comparisons: Edge labelled with corresponding bit
- Similar to Radix Sort: use individual bits, not the whole key
- You can also have compressed multiway tries