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, 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.
Info The Dictionary field uses a char key type. This is not essential. With this tree design, any value type could be used.
Finally Add and Get do a lookup in the Dictionary for the value specified. They return the DictionaryNode found, or null.
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 pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.
This page was last updated on Dec 24, 2024 (simplify).