TRIE
Trie data structure
or (radix tree(radix trie is compressed trie), prefix tree, digital tree)
A trie, also called digital tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated; i.e., the value of the key is distributed across the structure
Advantages:
1. Sometimes Space-Efficient. If you're storing lots of words that start with similar patterns, tries may reduce the overall storage cost by storing shared prefixes once.
2. Efficient Prefix Queries. Tries can quickly answer queries about words with shared prefixes, like:
How many words start with "choco"?
What's the most likely next letter in a word that starts with "strawber"?
Disadvantages:
1. Usually Space-Inefficient. Tries rarely save space when compared to storing strings in a set.
ASCII characters in a string are one byte each. Each link between trie nodes is a pointer to an address—eight bytes on a 64-bit system. So, the overhead of linking nodes together often outweighs the savings from storing fewer characters.
2. Not Standard. Most languages don't come with a built-in trie implementation. You'll need to implement one yourself.
Applications:
1. Dictionary
2. Spell checker applications
3. Autocomplete
Suffix trie:
Will Post in another Post
Trie vs BST:
Will post in another Post
Trie vs Hashing:
Will Post in another Post
srcs and refs:
- https://www.interviewcake.com/concept/java/trie
- https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014
- https://www.hackerearth.com/practice/data-structures/advanced-data-structures/trie-keyword-tree/tutorial/
- https://www.geeksforgeeks.org/advanced-data-structures/#Trie
- https://en.wikipedia.org/wiki/Trie
No comments:
Post a Comment