13.3. Longest Prefix Match with Trie

The Trie algorithm is described by Knuth.^[5] The addresses in the forwarding database are put into a tree data structure. Each vertex represents a prefix. The root consists of the zero-length prefix (which matches any address). There are two pointers from each vertex: a "1" and a "0." If no string in the dictionary contains the vertex's string plus the extra bit value, that pointer either is missing or points to a vertex indicating failure.

^[5] Donald E. Knuth, Sorting and Searching, vol. 3 of The Art of Computer Programming (Reading, Mass.: Addison-Wesley, 1973), 481–500.