Click here to Skip to main content
15,358,692 members
Articles / Web Development / ASP.NET
Posted 10 Jan 2004


124 bookmarked

Ternary Search Tree Dictionary in C#: Faster String Dictionary!

Rate me:
Please Sign up or sign in to vote.
4.57/5 (46 votes)
27 Jan 20043 min read
A TST is a fast and memory efficient data structure for implementing a string dictionary.

Sample Image - tst.png

Please comment your votes!


This article presents a ternary search tree dictionary (a symbol table) that is generally as fast as the Hashtable but also features new search possibilities. This new symbol table can be used in replacement of the other .Net dictionaries when the keys are strings. The main class behaves almost like any IDictionary table, to the difference that it accepts string key only.

This data structure supports also interesting search methods such as partial match and near-neighbor match. For instance, the near-neighbor search can be used to provide similar words while implementing an online thesaurus.

The ternary search tree dictionary implementation is based on the article of Jon L. Bentley and Robert Sedgewick, Fast Algorithms for Sorting and Searching Strings, cfr. [1].

The class comes with a full set of NUnit test, benchmarks with Hashtable and some utility to visualize the tree.

What is a ternary search tree ?

The ternary search tree (TST) is a dictionary data structure specially crafted for the situation where the key are string. It can find, remove and add keys quickly. It can also easily search the tree for partial matches -- auto matches autograph, automatic, and so on. In addition, you can implement near-match functions, which gives you the ability to suggest alternatives for misspelled words -- e.g., impliment matches implement.

A TST stores key-value pairs, where keys are strings and values are objects. In addition, TSTs use memory efficiently to store large quantities of data. Best of all, all of this magic is performed lightning fast (see benchmark). The tremendous flexibility of TSTs provides ample opportunity for creative programming.

The picture in the article front shows how the ternary tree is layout for 12 two letters words: as at be by he in is it of on or to.

How to use it ?

The TstDictionary implements the dictionary. It can be used as any other IDictionary based class, the only restriction being that key must be strings.

TstDictionary tst = new TstDictionary();

Add entries

tst.Add("hello", null);
// attach a value to the key
Object value = ...;
tst.Add("another key",value);

Remove entries


Clear dictionary


Iterate over entries

foreach(DictionaryEntry de in tst)
   // de.Key is the key,
   // de.Value is the value

Access elements

Object value = tst["hello"].Value;

Partial Match search

Partial match search with wild char character. Searching the dictionary for the pattern *o*o*o matches the single word rococo, while the pattern *a*a*a matches many words, including banana, casaba, and pajama:

foreach(DictionaryEntry de in tst.PartialMatch("*a*a"))
   // de.Key matches the pattern

Near-Neighbor search

This methods finds all words in the dictionary that are within a given Hamming distance of a query word. For instance, a search for all words within distance two of soda finds code, coma and 117 other words.

foreach(DictionaryEntry de in tst.NearNeighbors("a",1))
   // de.Key matches the pattern as, at, ma, ba, etc...

Why not implementing IDictionary ?

As mentionned in the introduction, the TstDictionary does not implement the IDictionary interface, although it implements all the methods needed. The rationale for this is to avoid confusing the user by letting him use non-string keys.


The TstDictionary class provides a Synchronized method to obtain a synchronized (thread-safe) wrapper of the dictionary. This wrapper behaves similarly to other .NET synchronized wrappers.


Addition benchmarks

Contains benchmarks


The Tst project is composed of the following projects:

  • Tst, a class library that contains the TST implementation,
  • Tst.Utility, a set of helper classes to visualize the TST modifications,
  • Tst.Tests, NUnit tests
  • Tst.Benchmark, benchmarks with Hashtable,
  • Tst.Console, demo application.

Todo list

  • The enumerator should iterate the keys in alphabetical order, which it does not... yet.


  • 11-01-2004, initial release.



This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Jonathan de Halleux
United States United States
Jonathan de Halleux is Civil Engineer in Applied Mathematics. He finished his PhD in 2004 in the rainy country of Belgium. After 2 years in the Common Language Runtime (i.e. .net), he is now working at Microsoft Research on Pex (

Comments and Discussions

Question[My vote of 1] Thanks for sharing the code, but the implementation is not efficient. Pin
sin2a2-Nov-12 5:40
Membersin2a2-Nov-12 5:40 
BugVery slow Pin
anprox6-Aug-12 21:15
Memberanprox6-Aug-12 21:15 
BugNode is not a key... Pin
mkha9827-Feb-12 16:47
Membermkha9827-Feb-12 16:47 
Generalserialization problem Pin
vemireddyramakrishnareddy10-May-09 20:01
Membervemireddyramakrishnareddy10-May-09 20:01 
GeneralNeat concept; skimpy explanation Pin
Shane Story19-Dec-08 9:09
MemberShane Story19-Dec-08 9:09 
GeneralWondering Pin
Preky12-Oct-07 22:52
MemberPreky12-Oct-07 22:52 
GeneralRe: Wondering Pin
kchvilyov27-Apr-08 3:32
Memberkchvilyov27-Apr-08 3:32 
Generali need some help Pin
stefan stoian12-Sep-06 5:06
Memberstefan stoian12-Sep-06 5:06 
GeneralWildcard Search Pin
Sanjot Dalvi6-Jun-06 18:08
MemberSanjot Dalvi6-Jun-06 18:08 
QuestionSome problem Pin
Vijay Kumar Raja Grandhi30-Mar-06 0:03
MemberVijay Kumar Raja Grandhi30-Mar-06 0:03 
GeneralNearest Neighbors not 100% accurate Pin
MaryJones11-Jan-06 13:04
MemberMaryJones11-Jan-06 13:04 
GeneralRe: Nearest Neighbors not 100% accurate Pin
Tomislav Kosutic26-Jan-06 23:15
MemberTomislav Kosutic26-Jan-06 23:15 
GeneralRe: Nearest Neighbors not 100% accurate Pin
Jesus Navarro27-Mar-08 6:46
MemberJesus Navarro27-Mar-08 6:46 
GeneralRe: Nearest Neighbors not 100% accurate Pin
kchvilyov27-Apr-08 3:28
Memberkchvilyov27-Apr-08 3:28 
GeneralNearest Neighbors Pin
MaryJones10-Jan-06 16:01
MemberMaryJones10-Jan-06 16:01 
GeneralRe: Nearest Neighbors Pin
MaryJones11-Jan-06 12:43
MemberMaryJones11-Jan-06 12:43 
QuestionHow to access via VB ? Pin
MaryJones10-Jan-06 12:21
MemberMaryJones10-Jan-06 12:21 
AnswerRe: How to access via VB ? Pin
MaryJones10-Jan-06 12:31
MemberMaryJones10-Jan-06 12:31 
GeneralRe: How to access via VB ? Pin
Christian Graus10-Jan-06 12:42
mveChristian Graus10-Jan-06 12:42 
GeneralNUnit.Framework Pin
Doncp5-Nov-05 9:02
MemberDoncp5-Nov-05 9:02 
Questionpartial match issue again Pin
jhrbek12-Sep-05 18:35
Memberjhrbek12-Sep-05 18:35 
GeneralExplicit Interface Implementation Pin
rokoprc24-Jun-05 0:56
Memberrokoprc24-Jun-05 0:56 
GeneralRe: Explicit Interface Implementation Pin
Anonymous24-Jun-05 5:27
MemberAnonymous24-Jun-05 5:27 
GeneralRe: Explicit Interface Implementation Pin
rokoprc26-Jun-05 22:41
Memberrokoprc26-Jun-05 22:41 
QuestionBut how does it work?? Pin
Alan C. Balkany24-Feb-05 3:51
MemberAlan C. Balkany24-Feb-05 3:51 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.