又稱單詞查找樹，Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來節(jié)約存儲空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
字典樹與字典很相似,當(dāng)你要查一個(gè)單詞是不是在字典樹中,首先看單詞的第一個(gè)字母是不是在字典的第一層,如果不在,說明字典樹里沒有該單詞,如果在就在該字母的孩子節(jié)點(diǎn)里找是不是有單詞的第二個(gè)字母,沒有說明沒有該單詞,有的話用同樣的方法繼續(xù)查找.字典樹不僅可以用來儲存字母,也可以儲存數(shù)字等其它數(shù)據(jù)。
Trie的數(shù)據(jù)結(jié)構(gòu)定義：
#define MAX 26
typedef struct Trie
{
Trie *next[MAX];
int v; //根據(jù)需要變化
};
Trie *root;
next是表示每層有多少種類的數(shù)，如果只是小寫字母，則26即可，若改為大小寫字母，則是52，若再加上數(shù)字，則是62了，這里根據(jù)題意來確定。
v可以表示一個(gè)字典樹到此有多少相同前綴的數(shù)目，這里根據(jù)需要應(yīng)當(dāng)學(xué)會自由變化。
Trie的查找（最主要的操作）：
(1) 每次從根結(jié)點(diǎn)開始一次搜索；
(2) 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索； (3) 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個(gè)字母,并進(jìn)一步選擇對應(yīng)的子樹進(jìn)行檢索。
(4) 迭代過程……
(5) 在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。
這里給出生成字典樹和查找的模版：
生成字典樹：
void createTrie(char *str)
{
int len = strlen(str);
Trie *p = root, *q;
for(int i=0; i<len; ++i)
{
int id = str[i]-'0';
if(p->next[id] == NULL)
{
q = (Trie *)malloc(sizeof(Trie));
q->v = 1; //初始v==1
for(int j=0; j<MAX; ++j)
q->next[j] = NULL;
p->next[id] = q;
p = p->next[id];
}
else
{
p->next[id]->v++;
p = p->next[id];
}
}
p->v = -1; //若為結(jié)尾，則將v改成-1表示
}
接下來是查找的過程了：
int findTrie(char *str)
{
int len = strlen(str);
Trie *p = root;
for(int i=0; i<len; ++i)
{
int id = str[i]-'0';
p = p->next[id];
if(p == NULL) //若為空集，表示不存以此為前綴的串
return 0;
if(p->v == -1) //字符集中已有串是此串的前綴
return -1;
}
return -1; //此串是字符集中某串的前綴
}
對于上述動態(tài)字典樹，有時(shí)會超內(nèi)存，比如
HDOJ 1671 Phone List，這是就要記得
釋放空間了：
int dealTrie(Trie* T)
{
int i;
if(T==NULL)
return 0;
for(i=0;i<MAX;i++)
{
if(T->next[i]!=NULL)
deal(T->next[i]);
}
free(T);
return 0;
}
題目分析+解答報(bào)告：
HDOJ 1251 統(tǒng)計(jì)難題：
http://www.wutianqi.com/?p=1364
HDOJ 1671 Phone List
http://www.wutianqi.com/?p=1366
這里還有幾個(gè)字典樹的相關(guān)資料，我上傳了RaySource里了，順便和大家分享下：
算法合集之《淺析字母樹在信息學(xué)競賽中的應(yīng)用》
字典樹
posted on 2010-09-24 09:17
Tanky Woo 閱讀(2228)
評論(1) 編輯 收藏 引用