Trie樹

     Trie樹，又稱為字典樹，是一種樹形結構，是一種哈希樹的變種，是一種用於快速檢索的多叉樹數據結構。典型應用是用於統計和排序、查詢大量的字符串但不僅限於字符串），所以經常被搜索引擎系統用於文本的詞頻統計等。

    找了一個簡單的小例子來實現trie樹的原理：

#include <iostream>
using namespace std;
const int branchNum = 26;
int i;
struct Trie_node
{
    bool isStr; //記錄此處是否構成一個串。
    Trie_node *next[branchNum];//指向各個子樹的指針,下標0-25代表26字符
    Trie_node():isStr(false)
    {
        memset(next,NULL,sizeof(next));
    }
};
class Trie
{
public:
    Trie();
    void insert(const char* word);
    bool search(char* word);
    void deleteTrie(Trie_node *root);
private:
    Trie_node* root;
};
Trie::Trie()
{
    root = new Trie_node();
}
void Trie::insert(const char* word)
{
    Trie_node *location = root;
    while(*word)
    {
        if(location->next[*word-'a'] == NULL)
        {
            Trie_node *tmp = new Trie_node();
            location->next[*word-'a'] = tmp;
        }   
        location = location->next[*word-'a'];
        word++;
    }
    location->isStr = true;
}
bool Trie::search(char *word)
{
    Trie_node *location = root;
    while(*word && location)
    {
        location = location->next[*word-'a'];
        word++;
    }
    return(location!=NULL && location->isStr);
}
void Trie::deleteTrie(Trie_node *root)
{
    for(i = 0; i < branchNum; i++)
    {
        if(root->next[i] != NULL)
        {
            deleteTrie(root->next[i]);
        }
    }
    delete root;
}
int main()
{
    Trie t;
    t.insert("a");        
    t.insert("abandon");
    char * c = "abandoned";
    t.insert(c);
    t.insert("abashed");
    if(t.search("abashed"))
        printf("true\n");
    return 0;
}

    如果有多個字符串需要用trie樹返回一個哈希值(不同的字符串返回的哈希值不相同)，則可以在每個節點存儲一個額外的值，也就是在上述代碼 isStr = true的情況下，會有個值來記錄它對應的哈希值hash_value;

   (1) 設置一個遞增變量v = 1;

   (2) 字符串數組 char *a[N];hash_v[N];

   (3) for(i=0;i<N;i++  )  hash_v[i] = insert(*a[i]);,  如果*a[i]字符串之前沒有出現過，hash_v[i]= v++;  否則hash_v[i] = (串尾節點的hash_value)。

    在字符串哈希中，如果要求的重復度不能高，則可以考慮用trie樹。