An edge label is the string stored on a radix-trie edge. It represents a compressed portion of a key, so one edge can stand for several character links. During traversal, compare the search string with the label, beginning with their first characters; the label need not match the entire remaining string. section 6.3.1
Edge-label matching produces four practical cases:
- The label completely matches the relevant beginning of the search string; continue from the destination node with the remaining suffix. section 6.3.1
- The label and search string share a shorter common prefix; split the label and insert a bridge node at that prefix. section 6.3.3
- The search string ends inside the label; handle the shorter key as a prefix of the existing edge. section 6.3.1
- No edge label shares a prefix with the search string; add a new edge for the remaining string. section 6.3.1
Splitting a partial match
Suppose an existing edge is labeled “anti” and “annual” is inserted. Their common prefix is “an”. Replace the original edge with an edge labeled “an” leading to a bridge node; attach “ti” to the old destination and “nual” to the new branch. section 6.3.3
Figure 6.13 An example of a radix trie node with edges stored as in sorted array. (Left) A failed binary search. (Right) A successful search. Comparisons are performed only on the first character of each string: in the successful search, though, the edge’s label is a prefix of the searched string.
Use the diagram to compare failed and successful edge selection when only the first character guides the search; the successful label is a prefix of the searched string. section 6.3.1
