Plant your data in a ternary search tree

Create an English dictionary that checks spelling and matches words as you type

By Wally Flint, JavaWorld.com, 02/16/01

Page 2 of 4

Say you wish to store tub, myObject in Figure 2's tree. Set currentChar to the key's (tub) first character, and set currentNode to the root node. Compare currentChar to the currentNode's splitchar; since both equal "t," set currentChar to the next character in tub and set currentNode to the equal kid -- the "o" node. Compare currentChar to "o." Since "u" comes after "o" in the alphabet, set currentNode to the hi kid, leaving currentChar unchanged. Since currentNode is null, create a new node, setting its splitchar to currentChar, "u." The new node will become the "o" node's hi kid. Now compare currentChar to the currentNode's splitchar; since both equal "u," set currentChar to the next character in the key and currentNode to the equal kid. Because currentNode is null, create a new node, setting its splitchar to currentChar, or "b." The new node will become the "u" node's equal kid. Compare currentChar to the currentNode's splitchar; both are equal to "b." You've reached the end of the key, so store myObject in currentNode -- the "b" node. Figure 3 depicts the new tree structure.

Figure 3. Figure 2's TST after
adding tub key. Click on thumb-
nail to view full size image.
(23 KB)

The example described above highlights an important characteristic of the TST data structure: Though tub has three characters, adding its key resulted in the addition of only two new tree nodes. That results because the TST reuses the "t" node (root node in Figure 2) in the representation of the new key, tub. Similarly, if you add a new key tool, only one more node (splitchar equal to 'l') would be required. Because the TST reuses nodes and because it creates nodes only when needed to represent new keys, the TST occupies little memory relative to many other data structures.

You've examined the basic storage and retrieval of data. Now explore how to find data having keys that only partially match a target string.

To find all nodes whose keys have a given prefix, simply find the node indexed by that prefix. Regard that node's equal child as a subtree's root node. Every node in the subtree represents a key that begins with the prefix. Since the tree (or subtree) structure maintains the alphabetical order of its keys, a recursive algorithm that retrieves a list of tree data will order the list according to the keys' alphabetical order.

What does it mean to find all nodes whose keys nearly match a target string? In this case, keys can differ from a target string by a specified number of characters. For example, impliment differs from implement by one character. An algorithm that implements that functionality can form the basis for dictionary spell-checking. The recursive algorithm below finds all keys differing from the target key by "d" characters:

matchAlmost(String key, int i, TSTNode currentNode, int d) {
    if((currentNode == null) || (d < 0) || (i == key.length())) return;
            
    // low branch
    if(key.charAt(i) < currentNode.splitchar) matchAlmost(key, i, currentNode.relatives[TSTNode.LOKID], d);
            
    //equal branch
    int nextD = (key.charAt(i) == currentNode.splitchar) ? d : d - 1;
    if((key.length() == i + 1) && (nextD == 0) && (currentNode.data != null)) {
        // add the key of the current node to the list of nearly matching keys
    }
    matchAlmost(key, i + 1, currentNode.relatives[TSTNode.EQKID], nextD);
    // hi branch
    if(key.charAt(i) > currentNode.splitchar) matchAlmost(key, i, currentNode.relatives[TSTNode.HIKID], d)
}

The algorithm above resembles the algorithm for finding matching keys, except that it regards a key character (currentChar) as matching a currentNode's splitchar when the characters actually match or when the current number of mismatching characters has not exceeded the desired number. Unlike the algorithm used in the get method, the algorithm above is recursive and can return multiple values.