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