A Trie (from re

**trie**val), 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