244 CHAPTER 11 Prefix-Match Lookups ROOT 0 P5 1 P4 0 1 P8 0 P6 0 1 0 1 P1 P3 1 P9 0 P2 0 1 0 P7 F I G U R E 11.7 The one-bit trie for the sample database of Figure 11.6. In Figure 11.7, this is done by using a text string (i.e. "01") to represent the pointers that would have been followed in the one-way branch. Thus in Figure 11.7, two trie nodes (containing two pointers apiece) in the path to P3 have been replaced by a single text string of 2 bits. Clearly, no information has been lost by this transformation. (As an exercise, determine if there is another path in the trie that can similarly be compressed.) To search for the longest matching prefix of a destination address D, the bits of D are used to trace a path through the trie. The path starts with the root and continues until search fails by ending at an empty pointer or at a text string that does not completely match. While following the path, the algorithm keeps track of the last prefix encountered at a node in the path. When search fails, this is the longest matching prefix that is returned. For example, if D begins with 1110, the algorithm starts by following the 1-pointer at the root to arrive at the node containing P4. The algorithm remembers P4 and uses the next bit of D (a 1) to follow the 1-pointer to the next node. At this node, the algorithm follows the 1-pointer to arrive at P2. When the algorithm arrives at P2, it overwrites the previously stored value (P4) by the newer prefix found (P2). At this point, search terminates, because P2 has no outgoing pointers. On the other hand, consider doing a search for a destination D whose first 5 bits are 11000. Once again, the first 1 bit is used to reach the node containing P4. P4 is remembered as the last prefix encountered, and the 1 pointer is followed to reach the rightmost node at height 2. The algorithm now follows the third bit in D (a 0) to the text string node containing "01." Thus we remember P9 as the last prefix encountered. The fourth bit of D is a 0, which matches