算法 - 查找树，最近路径preFIX回落 [英] algorithm - lookup tree with closest path prefix fallback

问题描述

我是一个算法的一个问题，我保持一个树形结构上，我需要找到最匹配的数据节点之后。如果没有精确匹配，就后退到最近的preFIX。

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.

举例来说，如果说我有下面的结构，其中的词（字编号）是分公司和用方括号中的数字数据（叶节点）;我是一个算法，该算法会回来与该组的结果如下表所示后。请注意，路径分隔符为＆gt;中

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

我一个C ++后，我真的很（ STL 或提升为主）库;只是指向一个漂亮的算法，这个目的是一样好。

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.

推荐答案

您正在寻找一个三元搜索树

You're looking for a Ternary Search Tree

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

这篇关于算法 - 查找树，最近路径preFIX回落的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！