具有最近路径前缀回退的查找树

Question

我正在寻找一种算法来解决一个问题，我维护一个树结构，我需要在树结构上找到数据节点的最接近匹配项。如果没有完全匹配项，它将回退到最接近的前缀。

例如，如果假设我有以下结构，其中单词（单词中的数字）是分支，带方括号的数字是数据（叶节点）;我追求的算法会返回下表所示的结果集。请注意，路径分隔符">"

           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)          |
+---------------------------+--------+---------------------------------------------+

我真的在追求一个C++（基于STL或boost）的库;但只是指向一个漂亮的算法来达到这个目的同样好。

Answer 1

您正在寻找三元搜索树

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