Beginning Algorithms

Chapter 14. Ternary Search Trees

So far, you've learned a number of ways to store data—from simple, unordered lists to sorted lists, binary search trees, and even hash tables. All of these are great for storing objects of arbitrary types. You're about to learn one last data structure for storing strings. It's not only fast to search, it also enables you to perform some quite different and interesting forms of searching.

This chapter discusses the following topics:

• General properties of ternary search trees

• How words are stored

• How words can be looked up

• How ternary search trees can be used for creating a dictionary

• How to implement a simple application to help solve crossword puzzles

Understanding Ternary Search Trees

Ternary search trees are specialized structures for storing and retrieving strings. Like a binary search tree, each node holds a reference to the smaller and larger values. However, unlike a binary search tree, a ternary search tree doesn't hold the entire value in each node. Instead, a node holds a single letter from a word, and another reference—hence ternary—to a subtree of nodes containing any letters that follow it in the word.

Figure 14-1 shows how you could store "cup," "ape," "bat," "map," and "man" in a ternary search tree. Notice that we have depicted the siblings—smaller and larger letters—as solid links, and the children—letters that follow—as dashed links.

Figure 14.1. A ...