C++

Forum

 
Search Trie for prefixes

rorschach14 (53)
Hi, I have implemented a Trie structure in C, and implemented insert and search function.

I have a problem with search. It returns only full words, and not prefixes (and I don't understand why)

What i want>
1
2
3
 
insert(&trie, "booking");
/*bool*/ search(&trie, "booking"); returns 1, its good
search(&trie, "boo"); returns 0, but I want it to return 1


Trie struct>
1
2
3
4
5
6
7
8
9
10
11
12
13
 
typedef struct trie_node trie_node_t;
struct trie_node
{
    int value;
    trie_node_t *children[ALPHABET_SIZE];
};

typedef struct trie trie_t;
struct trie
{
    trie_node_t *root;
    int count;
};


Search function>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
// Returns non zero, if key presents in trie
int search(trie_t *pTrie, char key[])
{
    int level;
    int length = strlen(key);
    int index;
    trie_node_t *pCrawl;

    pCrawl = pTrie->root;

    for( level = 0; level < length; level++ )
    {
        index = CHAR_TO_INDEX(key[level]);

        if( !pCrawl->children[index] )
        {
            return 0;
        }

        pCrawl = pCrawl->children[index];
    }

    return (0 != pCrawl && pCrawl->value);
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
Insert function>
void insert(trie_t *pTrie, char key[])
{
    int level;
    int length = strlen(key);
    int index;
    trie_node_t *pCrawl;

    pTrie->count++;
    pCrawl = pTrie->root;

    for( level = 0; level < length; level++ )
    {
        index = CHAR_TO_INDEX(key[level]);  //converts 'a' to 0, 'b' to 1 etc..
        if( !pCrawl->children[index] )
        {
            pCrawl->children[index] = getNode();
        }

        pCrawl = pCrawl->children[index];
    }

    // mark last node as leaf
    pCrawl->value = pTrie->count;
}
Last edited on
rorschach14 (53)
I think I solved it, LOL

I just changed>
return (0 != pCrawl && pCrawl->value);
to return 1; and it seems to work now.

If anybody sees any error please report it to me,
thanks.
doug4 (1538)
The reason your original failed is because you never assigned the value member of your trie node in your insert function, and the empty value field is anded to the return value.
Topic archived. No new replies allowed.