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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
