Java Performance Tuning

Search Trees

Here’s an alternate solution to the problem presented in the last section. I looked for a more obvious solution, another tree structure that would handle the search, provide full keyed access, and give plenty of scope for tuning. Jon Bentley and Bob Sedgewick^[81] detail a potential solution that offers an interesting structure and provides a good tuning exercise, so I will use it here.

A ternary tree is a three-way branching tree, i.e., each node has three branches. The structure is a halfway point between binary trees of strings (one string per node) and digital tries. A digital trie stores strings character by character, and has an n-way branching where n is the number of possible characters in the string (e.g., 26, if all strings have only lowercase alphabetic characters; 256, if strings can contain any 8-byte character; 34,000-way branching, if each node can be any Unicode character). Digitial tries are lightning-fast to search, but have exorbitant space costs that typically rule them out as a solution.

The ternary tree node searches by comparing the current character with the current node’s character. If equal, the next character in the string becomes the current character, and the node at the “equal” pointer becomes the current node. Otherwise, the current character in the string remains the current character, and the node at the “higher” or “lower” pointer becomes the current node. A TernarySearchTreeNode class has the Java class structure given as follows (the ...