Plant your data in a ternary search tree

Create an English dictionary that checks spelling and matches words as you type

The ternary search tree (TST) is the champion of data structure acrobatics -- it finds all keys having a given prefix, suffix, or infix. It even finds those keys that closely match a given pattern. You can 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. TST keys are stored and retrieved in sorted order, regardless of the order in which they are inserted into the tree. In addition, TSTs use memory efficiently to store large quantities of data. Best of all, all of this magic is performed lightning fast. The tremendous flexibility of TSTs provides ample opportunity for creative programming.

This article demonstrates three creative applications of the TST:

  • An English dictionary that matches words as you type and checks spelling
  • A flexible array that can assume any size or dimension on the fly
  • A database that stores all information in the same place (regardless of which record or column the information belongs to), thereby decreasing access time and reducing storage requirements

Let's begin with a demonstration of the dictionary application.

The dictionary applet

The applet below simulates an English dictionary that uses a TST to store dictionary data. To create this applet, I started with a list of roughly 48,000 words that I found on the Internet. (I can't promise that the list is complete or that all of the words are spelled accurately.) For each word, I created a definition equal to the string "Definition of the word " + currentWord + ".", and stored these key-value pairs (word, definition) in the TST.

1 2 Page
Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more