Tree, directed acyclic graph. A directed acyclic graph contains nodes that do not form cycles. It can be used to store strings from a word list—each letter is one node.
For search performance, an optimized tree is often the best solution. It has an initialization cost. And it requires some extra code to create. The C# version here is not optimal.
Example code. In the C# language a tree can be implemented with classes (nodes) that point to further nodes. In this simple implementation, we use a Dictionary.
Note AddWord() takes a string argument and adds it to the tree by creating (or using existing) nodes (one per character).
Note 2 ContainsWord() is similar to AddWord, but does not add anything. It just does lookups. It returns a bool.
Note 3 Add() will add a new DictionaryNode to the Dictionary if one does not exist. It one already exists, it will not add another.
Note 4 Get() retrieves a node from the tree from the current node—it uses a Dictionary lookup (TryGetValue).
using System;
using System.Collections.Generic;
class DictionaryNodeRoot
{
DictionaryNode _root = new DictionaryNode();
public void AddWord(string value)
{
// Add nodes from string chars.
DictionaryNode current = this._root;
for (int i = 0; i < value.Length; i++)
{
current = current.Add(value[i]);
}
// Set state.
current.SetWord(value);
}
public bool ContainsWord(string value)
{
// Get existing nodes from string chars.
DictionaryNode current = this._root;
for (int i = 0; i < value.Length; i++)
{
current = current.Get(value[i]);
if (current == null)
{
return false;
}
}
// Return state.
return current != null && current.GetWord() != null;
}
}
class DictionaryNode
{
string _word;
Dictionary<char, DictionaryNode> _dict; // Slow.
public DictionaryNode Add(char value)
{
// Add individual node as child.// ... Handle null field.
if (this._dict == null)
{
this._dict = new Dictionary<char, DictionaryNode>();
}
// Look up and return if possible.
DictionaryNode result;
if (this._dict.TryGetValue(value, out result))
{
return result;
}
// Store.
result = new DictionaryNode();
this._dict[value] = result;
return result;
}
public DictionaryNode Get(char value)
{
// Get individual child node.
if (this._dict == null)
{
return null;
}
DictionaryNode result;
if (this._dict.TryGetValue(value, out result))
{
return result;
}
return null;
}
public void SetWord(string word)
{
this._word = word;
}
public string GetWord()
{
return this._word;
}
}
class Program
{
static void Main()
{
// Create a tree.
DictionaryNodeRoot tree = new DictionaryNodeRoot();
// Add three words to the tree.
tree.AddWord("dot");
tree.AddWord("net");
tree.AddWord("perls");
// Search for strings in the tree.
Console.WriteLine(tree.ContainsWord("perls"));
Console.WriteLine(tree.ContainsWord("nothing"));
}
}True
False
Notes, above program. DictionaryNodeRoot serves as the root of the tree. It provides helper methods—AddWord and ContainsNode. We use this class to add strings to the tree.
Notes, AddWord. We add a string char-by-char with a for-loop in AddWord. The Add method from DictionaryNode.cs returns the newly-added or accessed node. We call Add repeatedly.
Notes, DictionaryNode. On each node, we use a Dictionary instance. The Dictionary provides references to child nodes. The string field tells us whether a complete word here exists.
Detail The Dictionary field uses a char key type. This is not essential. With this tree design, any value type could be used.
Notes, Add and Get. Add and Get are similar. Then they do a lookup in the Dictionary for the value specified. They return the DictionaryNode found, or null.
Notes, advantages. The tree accommodates vast data sets. This tree could handle any number of words within the limits of memory without a big performance drop.
Detail The design goal for this tree was simplicity. There are many ways to optimize the tree—see the performance section.
Warning Optimizations make the tree's design less obvious. They might not work for every requirement.
Notes, prefix search. With a tree, we can search just for prefixes—the entire key does not need to be known. This can avoid many substrings. It is critical for games like Scrabble.
A summary. This tree uses Dictionary fields for child nodes. It works with strings. Its design can be adapted to other value types. The nodes can be optimized with other representations.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on May 20, 2023 (simplify).