Поиск (НЕ с) подстановочных знаков внутри троичного дерева поиска

Я хочу изменить рекурсивную функцию из библиотеки «троичного дерева поиска» (SourceForge & http://code.google.com/p/ternary-search-tree/).
Поведение по умолчанию — искать в троичном дереве поиска все вхождения строк, которые соответствуют заданной подстановочной строке.
то есть, если в дереве есть «KEY», «KE1», «KE2», все записи будут найдены, если я буду искать «KE *».
Но мне нужно противоположное поведение — искать в троичном дереве поиска (которое содержит символы подстановки) все записи, которые соответствуют указанной строке.
то есть наличие в дереве «KE *», «KEY», «K *» должно найти все записи, если я ищу «KEY».

Дерево / узел определяется следующим образом:

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 — это указатель на вектор целых чисел, и функция get вызывается с корневым элементом и поисковым ключом в качестве аргумента. Я уже пытался приспособиться к этому, но пока не могу разобраться. Мой собственный код:

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 *» из дерева, он находит «K *» для поискового запроса «Key». Я до сих пор не понимаю, почему.

Есть идеи по этому поводу?

Приложение (мой тестовый пример):

#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;
}