Trie—單詞查找樹(shù)
l 簡(jiǎn)介
Trie，又稱單詞查找樹(shù)、前綴樹(shù)，是一種哈希樹(shù)的變種。應(yīng)用于字符串的統(tǒng)計(jì)與排序，經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。
含有單詞“tea”“tree”“A”“ZSU”的一棵Trie。
l 性質(zhì)
n 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。
n 從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
n 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。
l 優(yōu)點(diǎn)
n 查詢快。對(duì)于長(zhǎng)度為m的鍵值，最壞情況下只需花費(fèi)O(m)的時(shí)間；而BST最壞情況下需要O(m log n)的時(shí)間。
n 當(dāng)存儲(chǔ)大量字符串時(shí)，Trie耗費(fèi)的空間較少。因?yàn)殒I值并非顯式存儲(chǔ)的，而是與其他鍵值共享子串。
n Trie適用于“最長(zhǎng)前綴匹配”。
l 操作
n 初始化或清空
遍歷Trie，刪除所有節(jié)點(diǎn)，只保留根節(jié)點(diǎn)。
n 插入字符串
1. 設(shè)置當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，設(shè)置當(dāng)前字符為插入字符串中的首個(gè)字符；
2. 在當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)上搜索當(dāng)前字符，若存在，則將當(dāng)前節(jié)點(diǎn)設(shè)為值為當(dāng)前字符的子節(jié)點(diǎn)；否則新建一個(gè)值為當(dāng)前字符的子節(jié)點(diǎn)，并將當(dāng)前結(jié)點(diǎn)設(shè)置為新創(chuàng)建的節(jié)點(diǎn)。.
3. 將當(dāng)前字符設(shè)置為串中的下個(gè)字符，若當(dāng)前字符為0，則結(jié)束；否則轉(zhuǎn)2.
n 查找字符串
搜索過(guò)程與插入操作類似，當(dāng)字符找不到匹配時(shí)返回假；若全部字符都存在匹配，判斷最終停留的節(jié)點(diǎn)是否為樹(shù)葉，若是，則返回真，否則返回假。
n 刪除字符串
首先查找該字符串，邊查詢邊將經(jīng)過(guò)的節(jié)點(diǎn)壓棧，若找不到，則返回假；否則依次判斷棧頂節(jié)點(diǎn)是否為樹(shù)葉，若是則刪除該節(jié)點(diǎn)，否則返回真。
l 實(shí)現(xiàn)
對(duì)于字符表大小為S的字符串集，需建立一個(gè)S叉樹(shù)來(lái)代表這些字符串的集合。
l 代碼
trie.h
/**//** 版權(quán)所有 (C) 2009 喻揚(yáng) 中山大學(xué)
/* 本程序只作學(xué)習(xí)用途，未經(jīng)許可，不得用于任何商業(yè)目的。
*/
#include <string.h>
/**//* trie的節(jié)點(diǎn)類型 */
template <int Size> //Size為字符表的大小
struct trie_node 
{
/**//* 數(shù)據(jù)成員 */
bool terminable; //當(dāng)前節(jié)點(diǎn)是否可以作為字符串的結(jié)尾
int node; //子節(jié)點(diǎn)的個(gè)數(shù)
trie_node *child[Size]; //指向子節(jié)點(diǎn)指針
/**//* 構(gòu)造函數(shù) */
trie_node() : terminable(false), node(0) { memset(child, 0, sizeof(child)); }
};
/**//* trie */
template <int Size, typename Index> //Size為字符表的大小，Index為字符表的哈希函數(shù)
class trie {
public:
/**//* 定義類型別名 */
typedef trie_node<Size> node_type;
typedef trie_node<Size>* link_type;
/**//* 構(gòu)造函數(shù) */
trie(Index i = Index()) : index(i) {}
/**//* 析構(gòu)函數(shù) */
~trie() { clear(); }
/**//* 清空 */
void clear() {
clear_node(root);
for (int i = 0; i < Size; ++i) root.child[i] = 0;
}
/**//* 插入字符串 */
template <typename Iterator>
void insert(Iterator begin, Iterator end) {
link_type cur = &root; //當(dāng)前節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)
for (; begin != end; ++begin) {
if (!cur->child[index[*begin]]) { //若當(dāng)前字符找不到匹配，則新建節(jié)點(diǎn)
cur->child[index[*begin]] = new node_type;
++cur->node; //當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)加一
}
cur = cur->child[index[*begin]]; //將當(dāng)前節(jié)點(diǎn)設(shè)置為當(dāng)前字符對(duì)應(yīng)的子節(jié)點(diǎn)
}
cur->terminable = true; //設(shè)置存放最后一個(gè)字符的節(jié)點(diǎn)的可終止標(biāo)志為真
}
/**//* 插入字符串，針對(duì)C風(fēng)格字符串的重載版本 */
void insert(const char *str) { insert(str, str + strlen(str)); }
/**//* 查找字符串，算法和插入類似 */
template <typename Iterator>
bool find(Iterator begin, Iterator end) {
link_type cur = &root;
for (; begin != end; ++begin) {
if (!cur->child[index[*begin]]) return false;
cur = cur->child[index[*begin]];
}
return cur->terminable;
}
/**//* 查找字符串，針對(duì)C風(fēng)格字符串的重載版本 */
bool find(const char *str) { return find(str, str + strlen(str)); }
/**//* 刪除字符串 */
template <typename Iterator>
bool erase(Iterator begin, Iterator end) {
bool result; //用于存放搜索結(jié)果
erase_node(begin, end, root, result);
return result;
}
/**//* 刪除字符串，針對(duì)C風(fēng)格字符串的重載版本 */
bool erase(char *str) { return erase(str, str + strlen(str)); }
/**//* 按字典序遍歷單詞樹(shù) */
template <typename Functor>
void traverse(Functor &execute = Functor()) {
visit_node(root, execute);
}
private:
/**//* 訪問(wèn)某結(jié)點(diǎn)及其子結(jié)點(diǎn) */
template <typename Functor>
void visit_node(node_type cur, Functor &execute) {
execute(cur);
for (int i = 0; i < Size; ++i) {
if (cur.child[i] == 0) continue;
visit_node(*cur.child[i], execute);
}
}
/**//* 清除某個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn) */
void clear_node(node_type cur) {
for (int i = 0; i < Size; ++i) {
if (cur.child[i] == 0) continue;
clear_node(*cur.child[i]);
delete cur.child[i];
cur.child[i] = 0;
if (--cur.node == 0) break;
}
}
/**//* 邊搜索邊刪除冗余節(jié)點(diǎn)
返回值用于向其父節(jié)點(diǎn)聲明是否該刪除該節(jié)點(diǎn) */
template <typename Iterator>
bool erase_node(Iterator begin, Iterator end, node_type &cur, bool &result) {
if (begin == end) { //當(dāng)?shù)竭_(dá)字符串結(jié)尾：遞歸的終止條件
result = cur.terminable; //如果當(dāng)前節(jié)點(diǎn)可以作為終止字符，那么結(jié)果為真
cur.terminable = false; //設(shè)置該節(jié)點(diǎn)為不可作為終止字符，即刪除該字符串
return cur.node == 0; //若該節(jié)點(diǎn)為樹(shù)葉，那么通知其父節(jié)點(diǎn)刪除它
}
if (cur.child[index[*begin]] == 0) return result = false; //當(dāng)無(wú)法匹配當(dāng)前字符時(shí)，將結(jié)果設(shè)為假并返回假，
//即通知其父節(jié)點(diǎn)不要?jiǎng)h除它
else if (erase_node(++begin--, end, *(cur.child[index[*begin]]), result)) { //判斷是否應(yīng)該刪除該子節(jié)點(diǎn)
delete cur.child[index[*begin]]; //刪除該子節(jié)點(diǎn)
cur.child[index[*begin]] = 0; //子節(jié)點(diǎn)數(shù)減一
if (--cur.node == 0 && cur.terminable == false) return true; //若當(dāng)前節(jié)點(diǎn)為樹(shù)葉，那么通知其父節(jié)點(diǎn)刪除它
}
return false; //其他情況都返回假
}
/**//* 根節(jié)點(diǎn) */
node_type root;
/**//* 將字符轉(zhuǎn)換為索引的轉(zhuǎn)換表或函數(shù)對(duì)象 */
Index index;
};
l 參考資料
英文維基 http://en.wikipedia.org/wiki/Trie
中文維基 http://zh.wikipedia.org/w/index.php?title=Trie&variant=zh-cn