在三元搜索树中搜索(NOT with)通配符

Question

我想修改"三元搜索树"库中的递归函数(sourceforge&http://code.google.com/p/ternary-search-tree/)。默认行为是在三元搜索树中搜索与指定通配符字符串匹配的所有字符串。即，如果我搜索"KE*"，树中有"KEY"、"KE1"、"KE2"将找到所有条目。但我需要相反的行为——在三元搜索树(包含通配符)中搜索与指定字符串匹配的所有条目。即，如果我搜索"KEY"，则树中具有"KE*"、"KEY"、"K*"应能找到所有条目。

树/节点定义如下：

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的Vector的指针，函数get以根元素和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*"one_answers"Ke*"，它将只为"Key"找到一个解决方案(在本例中为Ke*)。如果我从树中删除"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 );
}
}