Tuesday, May 12, 2015

Trie

A Trie (from retrieval), is a multi-way tree structure useful for storing strings over an alphabet. It has been used to store large dictionaries of English (say) words in spelling-checking programs and in natural-language "understanding" programs. Using Trie, search complexities can be brought to optimal limit (key length).

Example:

Given the following strings:
an, ant, all, allot, alloy, aloe, are, ate, be
the corresponding Trie would be:


A simple implementation:

#define ALPHABET_SIZE 26
#include<string>

class Trie
{
public:
Trie();
void insert(std::string key);
int search(std::string key);
private:
struct Trie_Node
{
int value; //For leaf nodes
Trie_Node *children[ALPHABET_SIZE];
Trie_Node();
};
Trie_Node *m_root;
int m_count;
};

Trie::Trie_Node::Trie_Node():value(0)
{
for(int i = 0; i < ALPHABET_SIZE; ++i)
{
children[i] = 0;
}
}

Trie::Trie():m_root(new Trie_Node()), m_count(0)
{

}

void Trie::insert(std::string key)
{
int len = key.size();
Trie_Node *itr = m_root;
++m_count;
for(int i = 0; i < len; ++i)
{
int index = key[i] - 'a';
if(!itr->children[index])
itr->children[index] = new Trie_Node();
itr = itr->children[index];
}
itr->value = m_count;
}

int Trie::search(std::string key)
{
int len = key.size();
Trie_Node *itr = m_root;
for(int i = 0; i < len; ++i)
{
int index = key[i] - 'a';
if(!itr->children[index])
return 0;
itr = itr->children[index];
}
if(itr)
return itr->value;
return 0;
}

Complexity: O(n) for both insertion and search where n is the length of pattern

No comments:

Post a Comment