Exercise 23. Ternary Search Trees
The final data structure we’ll investigate is called a ternary search tree (
TSTree), and it’s useful for quickly finding a string in a set of strings. It’s similar to a
BSTree but instead of two children it has three children, and each child is only a single character rather than an entire string. In the
BSTree you had a left and right child for the “less-than” and “greater-than-equal” branches of the tree. With a
TSTree you have left, middle, and right branches for “less-than,” “equal-to,” and “greater-than” branches. This lets you take a string, break it into characters, and then walk the
TSTree one character at a time until you find it or you run out.
TSTree is effectively trading space for speed by breaking ...