Java Reference
In-Depth Information
1
0
0
1
120
0
0
1
0
1
0
24
0
1
0
1
0
0
1
2
7
32
37
40
42
Figure13.1
The binary trie for the collection of values 2, 7, 24, 31, 37, 40, 42,
120. All data values are stored in the leaf nodes. Edges are labeled with the value
of the bit used to determine the branching direction of each node. The binary
form of the key value determines the path to the record, assuming that each key is
represented as a 7-bit value representing a number in the range 0 to 127.
each node is (up to) 27. Once constructed, the alphabet trie is used to determine
if a given word is in the dictionary. Consider searching for a word in the alphabet
trie of Figure 13.2. The first letter of the search word determines which branch
to take from the root, the second letter determines which branch to take at the
next level, and so on. Only the letters that lead to a word are shown as branches.
In Figure 13.2(b) the leaf nodes of the trie store a copy of the actual words, while
in Figure 13.2(a) the word is built up from the letters associated with each branch.
One way to implement a node of the alphabet trie is as an array of 27 pointers
indexed by letter. Because most nodes have branches to only a small fraction of the
possible letters in the alphabet, an alternate implementation is to use a linked list of
pointers to the child nodes, as in Figure 6.9.
The depth of a leaf node in the alphabet trie of Figure 13.2(b) has little to do
with the number of nodes in the trie, or even with the length of the corresponding
string. Rather, a node's depth depends on the number of characters required to
distinguish this node's word from any other. For example, if the words “anteater”
and “antelope” are both stored in the trie, it is not until the fifth letter that the two
words can be distinguished. Thus, these words must be stored at least as deep as
level five. In general, the limiting factor on the depth of nodes in the alphabet trie
is the length of the words stored.
Poor balance and clumping can result when certain prefixes are heavily used.
For example, an alphabet trie storing the common words in the English language
would have many words in the “th” branch of the tree, but none in the “zq” branch.
Any multiway branching trie can be replaced with a binary trie by replacing the
original trie's alphabet with an equivalent binary code. Alternatively, we can use
the techniques of Section 6.3.4 for converting a general tree to a binary tree without
modifying the alphabet.
