Java Reference
In-Depth Information
0
1XXXXXX
0XXXXXX
1
120
00XXXXX
01XXXXX
2
3
0101XXX
000XXXX
24
4
4
5
010101X
2
7
32
37 40
42
Figure13.3
The PAT trie for the collection of values 2, 7, 24, 32, 37, 40, 42,
120. Contrast this with the binary trie of Figure 13.1. In the PAT trie, all data
values are stored in the leaf nodes, while internal nodes store the bit position used
to determine the branching decision, assuming that each key is represented as a 7-
bit value representing a number in the range 0 to 127. Some of the branches in this
PAT trie have been labeled to indicate the binary representation for all values in
that subtree. For example, all values in the left subtree of the node labeled 0 must
have value 0xxxxxx (where x means that bit can be either a 0 or a 1). All nodes in
the right subtree of the node labeled 3 must have value 0101xxx. However, we can
skip branching on bit 2 for this subtree because all values currently stored have a
value of 0 for that bit.
The trie implementations illustrated by Figures 13.1 and 13.2 are potentially
quite inefficient as certain key sets might lead to a large number of nodes with only
a single child. A variant on trie implementation is known as PATRICIA, which
stands for “Practical Algorithm To Retrieve Information Coded In Alphanumeric.”
In the case of a binary alphabet, a PATRICIA trie (referred to hereafter as a PAT
trie) is a full binary tree that stores data records in the leaf nodes. Internal nodes
store only the position within the key's bit pattern that is used to decide on the next
branching point. In this way, internal nodes with single children (equivalently, bit
positions within the key that do not distinguish any of the keys within the current
subtree) are eliminated. A PAT trie corresponding to the values of Figure 13.1 is
shown in Figure 13.3.
Example13.1
When searching for the value 7 (0000111 in binary) in
the PAT trie of Figure 13.3, the root node indicates that bit position 0 (the
leftmost bit) is checked first. Because the 0th bit for value 7 is 0, take the
left branch. At level 1, branch depending on the value of bit 1, which again
is 0. At level 2, branch depending on the value of bit 2, which again is 0. At
level 3, the index stored in the node is 4. This means that bit 4 of the key is
checked next. (The value of bit 3 is irrelevant, because all values stored in
that subtree have the same value at bit position 3.) Thus, the single branch
that extends from the equivalent node in Figure 13.1 is just skipped. For
key value 7, bit 4 has value 1, so the rightmost branch is taken. Because
