Created
September 26, 2017 02:52
-
-
Save runewake2/20bab89691ed241e0758ca48b810de65 to your computer and use it in GitHub Desktop.
A simple implementation of a Prefix Tree with the ability to Add words and Search for them.
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; | |
namespace Trees | |
{ | |
// Prefix Tree built for World of Zero: youtube.com/worldofzerodevelopment | |
public class PrefixTree | |
{ | |
private PrefixTreeNode root; | |
public PrefixTree() | |
{ | |
root = new PrefixTreeNode(String.Empty); | |
} | |
public void Add(string word) | |
{ | |
AddRecursive(root, word, String.Empty); | |
} | |
private void AddRecursive(PrefixTreeNode node, string remainingString, string currentString) | |
{ | |
if (remainingString.Length <= 0) | |
{ | |
return; | |
} | |
char prefix = remainingString[0]; | |
string substring = remainingString.Substring(1); | |
if (!node.SubNodes.ContainsKey(prefix)) | |
{ | |
node.SubNodes.Add(prefix, new PrefixTreeNode(currentString + prefix)); | |
} | |
if (substring.Length == 0) | |
{ | |
node.SubNodes[prefix].IsWord = true; | |
return; | |
} | |
else | |
{ | |
AddRecursive(node.SubNodes[prefix], substring, currentString + prefix); | |
} | |
} | |
public IEnumerable<string> Search(string searchString) | |
{ | |
PrefixTreeNode node = root; | |
foreach (var search in searchString) | |
{ | |
if (!node.SubNodes.ContainsKey(search)) | |
{ | |
return new string[0]; | |
} | |
node = node.SubNodes[search]; | |
} | |
return FindAllWordsRecursive(node); | |
} | |
private IEnumerable<string> FindAllWordsRecursive(PrefixTreeNode node) | |
{ | |
if (node.IsWord) | |
{ | |
yield return node.Word; | |
} | |
foreach (var subnode in node.SubNodes) | |
{ | |
foreach (var result in FindAllWordsRecursive(subnode.Value)) | |
{ | |
yield return result; | |
} | |
} | |
} | |
protected class PrefixTreeNode | |
{ | |
private readonly Dictionary<char, PrefixTreeNode> subNodes; | |
private bool isWord; | |
private readonly string word; | |
public PrefixTreeNode(string word) | |
{ | |
subNodes = new Dictionary<char, PrefixTreeNode>(); | |
isWord = false; | |
this.word = word; | |
} | |
public Dictionary<char, PrefixTreeNode> SubNodes { get { return subNodes; } } | |
public bool IsWord { get { return isWord; } set { isWord = value; } } | |
public string Word { get { return word; } } | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment