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
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 ...