Tries - Eishaaya/GMRDataStructuresTest GitHub Wiki
A Trie is a type of a search tree based on the prefix of the string. They are use to represent the "Retrieval" of data and thus the name Trie. It stores a set of strings as a tree of characters. All the descendants of the node have a common prefix of the string associated with that node, and the root is associated with the empty string. Keys generally tend to be associated with leaves, although some inner nodes may correspond with keys of interest. Therefore, keys are not necessarily associated with every node.
The prefix of a string is just any n letters where n <= string length.
For example, the word "abacaba" has the following prefixes:
a
ab
aba
abac
abaca
abacab
abacaba
Sometimes a trie can be space efficient. If the goal is to store a lot of words that start with similar patterns, tries may reduce the overall storage cost by storing shared prefixes once.
Efficient prefix queries. Tries can quickly answer queries about words with shared prefixes, like:
-
How many words begin with "wool"?
-
What is most likely next letter in a word that begins with "oran"?
Lookup in a trie is faster in the worst case at O(k) time, where k is the length of the string.
When compared to storing strings in a Binary Search Tree, Trie is faster because it is an O(k) operation where k is the length of the string, and in a BST it would be O(k * log(N)) where N is the number of keys in the tree.
There are no collisions of different keys in a trie when compared to a hash table.
There is no need to provide a hash function or to change hash functions as more keys are added to a trie.
Usually space inefficient. Tries rarely save space when compared to storing strings in a set. There is some overhead cost associated with tries.
Tries are generally not part of any standard libraries and require user implementation.
Some applications of the Trie data structure include word autocompletion suggestions, a spell checker, and various string processing strategies.
TrieNode class:
public class TrieNode
{
public char Letter { get; private set; }
public Dictionary<char, TrieNode> Children { get; private set; }
public bool IsWord { get; set; }
public TrieNode(char c)
{
Children = new Dictionary<char, TrieNode>();
Letter = c;
IsWord = false;
}
}Trie class:
public class Trie
{
public void Clear();
public void Insert(string word);
public bool Contains(string word);
private TrieNode SearchNode(string word);
public List<string> GetAllMatchingPrefix(string prefix);
public bool Remove(string prefix);
}- Iterate over the string and add it to the root's children if the current character does not exist and update the current root as you go down the tree.
- The simplest method is to check if the node representing the prefix exists, if it does not, we return false.
- If the node representing the prefix exists, then we unmark the node as the end of a word and return true.
- Iterate over the characters in the prefix and retrieve the corresponding TrieNode, once you have reached the end of the string, return the TrieNode representing the last matching character of the prefix.
- Depth First Search down the matching nodes, and add the word to a List if its a full word, return the list.
- Read words from this dictionary json file and provide the user with word suggestions as they type a word.
- Provide the user with the definition of the word, if it does not exist, then suggest them similar words (based on prefix) that do have a definition.