在三元搜索樹內搜索（不帶）通配符

Question

我想修改'三元搜索樹'庫中的遞歸函數（sourceforge & http://code.google.com/p/ternary-search-tree/）。 默認行爲是在三進制搜索樹中搜索匹配指定通配符字符串的所有字符串匹配。 即，如果我搜索'KE *'，樹中的'KEY'，'KE1'，'KE2'將會找到所有的entrys。 但我需要相反的行爲 - 在三元搜索樹（包含通配符）中搜索與指定字符串匹配的所有entrys。 即在我搜索'KEY'的情況下，樹中的'KE *'，'KEY'，'K *'應該找到所有的entrys。

樹/節點定義如下：

typedef struct TstNode { 
    TstNode(char c) : splitChar(c), left(0), right(0), mid(0){ 
    } 
    char splitChar; 
    TstTree left, right; 
    union { 
     TstTree mid; 
     int index; 
    }; 
} tstNode; 

並與默認行爲的功能：

template <class Object> 
void TernarySearchTree<Object>::partialMatchSearch(TstTree tree, const char *key) 
{ 
    if (!tree) return; 

    // partial match left 
    if (*key == '?' || *key == '*' || *key < tree->splitChar) 
    { 
     partialMatchSearch(tree->left, key); 
    } 
    // partial match middle 
    if (*key == '?' || *key == '*' || *key == tree->splitChar) 
    { 
     if (tree->splitChar && *key) 
     { 
      if (*key == '*') 
      { 
       partialMatchSearch(tree->mid, key); 
      } 
      else 
      { 
       partialMatchSearch(tree->mid, key+1); // search next pattern char 
      } 
     } 
    } 
    if ((*key == 0 || *key == '*') && tree->splitChar == 0) 
    { 
     pmVectorPtr->add(tree->index); 
    } 

    if (*key == '?' || *key == '*' || *key > tree->splitChar) 
    { 
     partialMatchSearch(tree->right, key); 
    } 
} 

pmVectorPtr是一個指向int的指針的一個向量和函數來獲取的調用根元素和searchkey作爲參數。我已經嘗試過適應這種情況，但還是無法擺脫困境。我自己的代碼：

template <class Object> 
void TernarySearchTree<Object>::partialMatchSearchInverted(TstTree tree, const char *key) 
{ 
    if (!tree) return; 

    if((tree->splitChar == '*') && (*key != 0)){ 
     partialMatchSearchInverted(tree, key+1); 
    } 

    if(*key != 0){ 
     if (*key < tree->splitChar){ 
      partialMatchSearchInverted(tree->left, key); 
     } 
     if (*key > tree->splitChar){ 
      partialMatchSearchInverted(tree->right, key); 
     } 
    } 
    if ((*key == tree->splitChar) || (tree->splitChar == '*')){ 
     if (tree->splitChar || *key){ 
      partialMatchSearchInverted(tree->mid, key+1); // search next pattern char 
     } 
    } 
    if ((*key == 0) && (tree->splitChar == 0)){ 
     pmVectorPtr->add(tree->index); 
    } 
} 

我已經廣泛使用調試器的編碼這一點，據我所知，這似乎是「工作（即使通配符是在一個字符串的開頭或中間） 。但是如果我在例子中添加'K *'和'Ke *'，它只會找到一個解決方案（在這種情況下，Ke *）爲'Key'。如果我從樹中刪除'Ke *'，它會爲'Key'的搜索查詢找到'K *'。我仍然不明白爲什麼。

有關於此的任何想法？

---

附錄（我的測試用例）：

#include <iostream> 
#include "ternarySearchTree/ternarySearchTree.h" 

int main(int argc, char *argv[]){ 
    TernarySearchTree<string> tst; 
    Vector< TstItem<String> > itemVector; 
    { 
     TstItem<String> item("Ke*", "Value"); 
     itemVector.add(item); 
    } 
    { 
     TstItem<String> item("K*", "Value"); 
     itemVector.add(item); 
    } 
    { 
     TstItem<String> item("Ka*", "Value"); 
     itemVector.add(item); 
    } 
    tst.buildBalancedTree(itemVector); 

    Vector<int> matches = tst.partialMatchSearchInverted("Key");// will only find Ke* (wrong - it should find Ke* and K*), if I remove Ke* above it would find K* (right), if I remove that also it would find nothing (also right) 
    for (unsigned j=0;j<matches.count();j++) 
    { 
     std::cout<<"Matching: "<< tst.getKey(matches[j]) <<" - "<< tst.getValue(matches[j])->c_str()<<std::endl; 
    } 
    std::cout<<"total matches "<< matches.count()<<std::endl; 
    return 0; 
} 

Answer 1

好了，我終於可以追蹤我的問題：我還沒有明白一個三叉樹究竟是如何工作的。因此，當通配符可能位於這些分支內部時，我沒有訪問左右節點（遺憾的是幾乎每次都是這樣）。所以我的最終算法比三元樹中的搜索要慢得多（恐怕複雜度可能類似於O（n）），但至少我已經將它運用了。

所以看起來這個數據結構不適合我的需要（搜索通配符字符串） - 我可能會得到與線性列表相同的速度。然而，如果某個有類似問題的人有一天會發現這個問題，這裏是我的代碼（但我不建議在實際應用程序中使用它，因爲它很慢，我想還有其他的結構，可以更好地處理這些問題）：

template <class Object> 
void TernarySearchTree<Object>::partialMatchSearchInverted(TstTree tree, const char *key) 
{ 
    if (!tree) return; 
    if((tree->splitChar == '*') && (*key != 0)){ 
     partialMatchSearchInverted(tree, key+1); // wildcard occured, search same node with next key 
    } 
    if(*key != 0){ 
     if (*key < tree->splitChar){ 
      partialMatchSearchInverted(tree->left, key); 
     }else if('*' < tree->splitChar){ // a wildcard could be in this branch 
      partialMatchSearchInverted(tree->left, key); 
     } 
     if (*key > tree->splitChar){ 
      partialMatchSearchInverted(tree->right, key); 
     }else if('*' > tree->splitChar){ // a wildcard could be here too 
      partialMatchSearchInverted(tree->right, key); 
     } 
    } 
    if ((*key == tree->splitChar) || (tree->splitChar == '*')){ 
     if (*key != 0){ 
      partialMatchSearchInverted(tree->mid, key+1); // search next pattern char 
     } 
    } 
    if ((*key == 0) && (tree->splitChar == 0)){ 
     pmVectorPtr->add(tree->index); 
    } 
}