algorithm - lookup tree with closest path prefix fallback

Question

I am after an algorithm for a problem where I maintain a tree structure on which I need to find the closest match for a data node. If no exact match, it falls back to the closest prefix.

For example, if say I have the below structure, where the words (number in words) are the branches and the numbers with square brackets are data (leaf node); I am after an algorithm that would come back with the set of results as shown in table below. Please note that the path separator is ">"

           one - [1]
            /\
         two  five
         /\       \
    eight  [12]    nine
   /                  \
 [128]                [159]


+---------------------------+--------+---------------------------------------------+
| path                      | result |                                             |
+---------------------------+--------+---------------------------------------------+
| one > five > nine         |    159 | whole path matches                          |
| one > five                |      1 | partial (only "one" matched)                |
| one > two > eight         |    128 | whole path matches                          |
| one > two                 |     12 | whole path matches                          |
| one > two > eight > seven |    128 | partial (only "one > two > eight" matched)  |
| one > two > seven         |     12 | partial (only "one > two" matched)          |
+---------------------------+--------+---------------------------------------------+

I am really after a C++ ( STL or boost based ) library; but just pointers to a nifty algorithm for this purpose would be equally good.

Answer 1

You're looking for a Ternary Search Tree

http://en.wikipedia.org/wiki/Ternary_search_tree