Last active
April 22, 2018 21:35
-
-
Save efruchter/c699a75420363c95b1ad to your computer and use it in GitHub Desktop.
A Trie implementation in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
/** | |
* A space-saving data structure to store words and their counts. | |
* Words that share prefixes will have common paths along a branch of the tree. | |
*/ | |
public class Trie | |
{ | |
private TrieNode head; | |
public Trie () | |
{ | |
head = new TrieNode(); | |
} | |
/** | |
* Add a word to the trie. | |
* Adding is O (|A| * |W|), where A is the alphabet and W is the word being searched. | |
*/ | |
public void AddWord(string word) | |
{ | |
TrieNode curr = head; | |
curr = curr.GetChild (word [0], true); | |
for (int i = 1; i < word.Length; i++) | |
{ | |
curr = curr.GetChild (word [i], true); | |
} | |
curr.AddCount (); | |
} | |
/** | |
* Get the count of a partictlar word. | |
* Retrieval is O (|A| * |W|), where A is the alphabet and W is the word being searched. | |
*/ | |
public int GetCount(string word) | |
{ | |
TrieNode curr = head; | |
foreach (char c in word) | |
{ | |
curr = curr.GetChild (c); | |
if (curr == null) | |
{ | |
return 0; | |
} | |
} | |
return curr.count; | |
} | |
internal class TrieNode | |
{ | |
private LinkedList<TrieNode> children; | |
public int count { private set; get; } | |
public char data { private set; get; } | |
public TrieNode(char data = ' ') | |
{ | |
this.data = data; | |
count = 0; | |
children = new LinkedList<TrieNode>(); | |
} | |
public TrieNode GetChild(char c, bool createIfNotExist = false) | |
{ | |
foreach (var child in children) | |
{ | |
if (child.data == c) | |
{ | |
return child; | |
} | |
} | |
if (createIfNotExist) | |
{ | |
return CreateChild (c); | |
} | |
return null; | |
} | |
public void AddCount() | |
{ | |
count++; | |
} | |
public TrieNode CreateChild(char c) | |
{ | |
var child = new TrieNode (c); | |
children.AddLast (child); | |
return child; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I have a file and do not need to search for some of the data in this file, for example, I want to search for all the words that are related to the word hello in that the file . how i can do this search with trie?