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.

The TSTree is effectively trading space for speed by breaking ...

Get Learn More Python 3 the Hard Way: The Next Step for New Python Programmers now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.