Exercise 46: Ternary Search Tree

The final data structure that I'll show you is called the TSTree, which is similar to the BSTree, except it has three branches: low, equal, and high. It's primarily used just like BSTree and Hashmap to store key/value data, but it works off of the individual characters in the keys. This gives the TSTree some abilities that neither BSTree nor Hashmap has.

In a TSTree, every key is a string, and it's inserted by walking through and building a tree based on the equality of the characters in the string. It starts at the root, looks at the character for that node, and if it's lower, equal to, or higher than that, then it goes in that direction. You can see this in the header file: