1.綜述

又稱單詞查找樹，Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。

它的優(yōu)點(diǎn)是：利用字符串的公共前綴來節(jié)約存儲(chǔ)空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

Trie樹結(jié)構(gòu)的優(yōu)點(diǎn)在于：

1） 不限制子節(jié)點(diǎn)的數(shù)量；

2） 自定義的輸入序列化，突破了具體語(yǔ)言、應(yīng)用的限制，成為一個(gè)通用的框架；

3） 可以進(jìn)行最大Tokens序列長(zhǎng)度的限制；

4） 根據(jù)已定閾值輸出重復(fù)的字符串；

5） 提供單個(gè)字符串頻度查找功能；

6） 速度快，在兩分鐘內(nèi)完成1998年1月份人民日?qǐng)?bào)（19056行）的重復(fù)字符串抽取工作。

2.性質(zhì)

它有3個(gè)基本性質(zhì)：

1)     根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。

2)     從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。

3)     每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

3.基本操作

其基本操作有:查找、插入和刪除,當(dāng)然刪除操作比較少見.我在這里只是實(shí)現(xiàn)了對(duì)整個(gè)樹的刪除操作,至于單個(gè)word的刪除操作也很簡(jiǎn)單.

4.實(shí)現(xiàn)方法

搜索字典項(xiàng)目的方法為：

　　(1) 從根結(jié)點(diǎn)開始一次搜索；

　　(2) 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對(duì)應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索；

　　(3) 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個(gè)字母,并進(jìn)一步選擇對(duì)應(yīng)的子樹進(jìn)行檢索。

　　(4) 迭代過程……

(5) 在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。

其他操作類似處理

5. Trie原理——Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。

6.代碼實(shí)現(xiàn)

代碼如下:

const int branchNum = 26; //聲明常量

int i;

struct Trie_node

{

       boolisStr;                //記錄此處是否構(gòu)成一個(gè)串。

       Trie_node*next[branchNum];//指向各個(gè)子樹的指針,下標(biāo)0-25代表26字符

       Trie_node():isStr(false)

       {

              memset(next,NULL,sizeof(next));

       }

};

class Trie

{

 public:

     Trie();

     voidinsert(const char* word);

     boolsearch(char* word);

     voiddeleteTrie(Trie_node *root);

       // voidprintTrie(Trie_node *root);   //new add

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']; //每插入一步，相當(dāng)于有一個(gè)新串經(jīng)過，指針要向下移動(dòng)

       word++;

    }

   location->isStr = true; //到達(dá)尾部,標(biāo)記一個(gè)串

 }

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]);

              }

       }

       deleteroot;

}

void main() //簡(jiǎn)單測(cè)試

{

       Trie t;

       t.insert("a");       

       t.insert("abandon");

       char * c= "abandoned";

       t.insert(c);

       t.insert("abashed");

       if(t.search("abashed"))

       {

          printf("true\n");  //已經(jīng)插入了

       }

}

有時(shí)，我們會(huì)碰到對(duì)字符串的排序，若采用一些經(jīng)典的排序算法，則時(shí)間復(fù)雜度一般為O(n*lgn)，但若采用Trie樹，則時(shí)間復(fù)雜度僅為O(n)。

Trie樹又名字典樹，從字面意思即可理解，這種樹的結(jié)構(gòu)像英文字典一樣，相鄰的單詞一般前綴相同，之所以時(shí)間復(fù)雜度低，是因?yàn)槠洳捎昧艘钥臻g換取時(shí)間的策略。

下圖為一個(gè)針對(duì)字符串排序的Trie樹(我們假設(shè)在這里字符串都是小寫字母)，每個(gè)結(jié)點(diǎn)有26個(gè)分支，每個(gè)分支代表一個(gè)字母，結(jié)點(diǎn)存放的是從root節(jié)點(diǎn)到達(dá)此結(jié)點(diǎn)的路經(jīng)上的字符組成的字符串。

將每個(gè)字符串插入到trie樹中，到達(dá)特定的結(jié)尾節(jié)點(diǎn)時(shí)，在這個(gè)節(jié)點(diǎn)上進(jìn)行標(biāo)記，如插入"afb"，第一個(gè)字母為a，沿著a往下，然后第二個(gè)字母為f，沿著f往下，第三個(gè)為b，沿著b往下，由于字符串最后一個(gè)字符為'\0'，因而結(jié)束，不再往下了，然后在這個(gè)節(jié)點(diǎn)上標(biāo)記afb.count++，即其個(gè)數(shù)增加1.

之后，通過前序遍歷此樹，即可得到字符串從小到大的順序。

實(shí)現(xiàn)代碼如下（g++、VC++都編譯通過）：

代碼如下:

#include <iostream>

#include <string.h>

using namespace std;

#define NUM 26

class Node

{

public:

    int count; //記錄該處字符串個(gè)數(shù)

    Node* char_arr[NUM];  //分支

    char* current_str;   //記錄到達(dá)此處的路徑上的所有字母組成的字符串

    Node();

};

class Trie

{

public:

    Node* root;

    Trie();

    void insert(char* str);

    void output(Node* &node, char** str, int& count);

};

//程序未考慮delete動(dòng)態(tài)內(nèi)存

int main()

{

    char** str = new char*[12];

    str[0] = "zbdfasd";

    str[1] = "zbcfd";

    str[2] = "zbcdfdasfasf";

    str[3] = "abcdaf";

    str[4] = "defdasfa";

    str[5] = "fedfasfd";

    str[6] = "dfdfsa";

    str[7] = "dadfd";

    str[8] = "dfdfasf";

    str[9] = "abcfdfa";

    str[10] = "fbcdfd";

    str[11] = "abcdaf";

    //建立trie樹

    Trie* trie = new Trie();

    for(int i = 0; i < 12; i++)

        trie->insert(str[i]);

    int count = 0;

    trie->output(trie->root, str, count);

    for(int i = 0; i < 12; i++)

        cout<<str[i]<<endl;

    return 0;

}

Node::Node()

{

    count = 0;

    for(int i = 0; i < NUM; i++)

        char_arr[i] = NULL;

    current_str = new char[100];

    current_str[0] = '\0';

}

Trie::Trie()

{

    root = new Node();

}

void Trie::insert(char* str)

{

    int i = 0;

    Node* parent = root;

    //將str[i]插入到trie樹中

    while(str[i] != '\0')

    {

        //如果包含str[i]的分支存在，則新建此分支

        if(parent->char_arr[str[i] - 'a'] == NULL)

        {

            parent->char_arr[str[i] - 'a'] = new Node();

            //將父節(jié)點(diǎn)中的字符串添加到當(dāng)前節(jié)點(diǎn)的字符串中

            strcat(parent->char_arr[str[i] - 'a']->current_str, parent->current_str);

            char str_tmp[2];

            str_tmp[0] = str[i];

            str_tmp[1] = '\0';

            //將str[i]添加到當(dāng)前節(jié)點(diǎn)的字符串中

            strcat(parent->char_arr[str[i] - 'a']->current_str, str_tmp);

            parent = parent->char_arr[str[i] - 'a'];

        }

        else

        {

            parent = parent->char_arr[str[i] - 'a'];

        }

        i++;

    }

    parent->count++;

}

//采用前序遍歷

void Trie::output(Node* &node, char** str, int& count)

{

    if(node != NULL)

    {

        if(node->count != 0)

        {

            for(int i = 0; i < node->count; i++)

                str[count++] = node->current_str;

        }

        for(int i = 0; i < NUM; i++)

        {

            output(node->char_arr[i], str, count);

        }

    }

}

更多信息請(qǐng)查看IT技術(shù)專欄