A trie is a special tree that can compactly store strings.
Tries are an extremely special and useful data-structure that are based on the prefix of a string. They are used to represent the “Retrieval” of data and thus the name Trie.
Here’s a trie that stores “David”, “Maria”, and “Mario”:
class TrieNode
{
public Dictionary Children { get; set; }
public bool EndOfWord { get; set; }
public TrieNode()
{
Children = new Dictionary();
}
}
class Trie
{
TrieNode root;
public Trie()
{
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void Insert(string word)
{
TrieNode current = root;
for (int i = 0; i < word.Length; i++)
{
char ch = word[i];
TrieNode node = current.Children[ch];
if (node == null)
{
node = new TrieNode();
current.Children.Add(ch, node);
}
current = node;
}
//mark the current nodes endOfWord as true
current.EndOfWord = true;
}
/**
* Recursive implementation of insert into trie
*/
public void InsertRecursive(String word)
{
InsertRecursive(root, word, 0);
}
private void InsertRecursive(TrieNode current, string word, int indx)
{
if (indx == word.Length - 1)
{
current.EndOfWord = true;
return;
}
char ch= word[indx];
current.Children.TryGetValue(ch,out TrieNode node);
if (node == null)
{
node = new TrieNode();
current.Children.Add(ch, node);
}
current.Children.Add(ch, node);
InsertRecursive(node, word, indx + 1);
}
/** Returns if the word is in the trie. */
public bool Search(string word)
{
TrieNode current = root;
for (int i = 0; i < word.Length; i++)
{
char ch = word[i];
current.Children.TryGetValue(ch, out TrieNode node);
//if node does not exist for given char then return false
if (node == null)
{
return false;
}
current = node;
}
//return true of current's endOfWord is true else return false.
return current.EndOfWord;
}
public bool StartsWith(string prefix)
{
TrieNode current = root;
for (int i = 0; i < prefix.Length; i++)
{
char ch = prefix[i];
current.Children.TryGetValue(ch, out TrieNode node);
//if node does not exist for given char then return false
if (node == null)
{
return false;
}
current = node;
}
//return true of current's endOfWord is true else return false.
return true;
}
}
supported operations:
1: Insert
2:Search
Site Title 