c++ - アルゴリズム - 最も近いパス プレフィックス フォールバックを使用したルックアップ ツリー

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