Trie，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

性質

它有3個基本性質：

根節點不包含字符，除根節點外每一個節點都只包含一個字符。

從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。

每個節點的所有子節點包含的字符都不相同。

[編輯]圖示

這是一個Trie結構的例子：

在這個Trie結構中，保存了A、to、tea、ted、ten、i、in、inn這8個字符串，僅占用8個字節（不包括指針占用的空間）。

實例

這是一個用于詞頻統計的程序范例，因使用了getline(3)，所以需要glibc才能鏈接成功，沒有glibc的話可以自行改寫。代碼由User:JohnBull捐獻，遵從GPL版權聲明。

#include <stdio.h> #include <stdlib.h> #include <string.h>#define TREE_WIDTH 256#define WORDLENMAX 128struct trie_node_st {int count;struct trie_node_st *next[TREE_WIDTH]; };static struct trie_node_st root={0, {NULL}};static char *spaces=" \t\n/.\"\'()";static int insert(const char *word) {int i;struct trie_node_st *curr, *newnode;if (word[0]=='\0') {return 0;}curr = &root;for (i=0; ; ++i) {if (curr->next[ word[i] ] == NULL) {newnode=(struct trie_node_st*)malloc(sizeof(struct trie_node_st));memset(newnode, 0, sizeof(struct trie_node_st));curr->next[ word[i] ] = newnode;}if (word[i] == '\0') {break;}curr = curr->next[ word[i] ];}curr->count ++;return 0; }static void printword(const char *str, int n) {printf("%s\t%d\n", str, n); }static int do_travel(struct trie_node_st *rootp) {static char worddump[WORDLENMAX+1];static int pos=0;int i;if (rootp == NULL) {return 0;}if (rootp->count) {worddump[pos]='\0';printword(worddump, rootp->count);}for (i=0;i<TREE_WIDTH;++i) {worddump[pos++]=i;do_travel(rootp->next[i]);pos--;}return 0; }int main(void) {char *linebuf=NULL, *line, *word;size_t bufsize=0;int ret;while (1) {ret=getline(&linebuf, &bufsize, stdin);if (ret==-1) {break;}line=linebuf;while (1) {word = strsep(&line, spaces);if (word==NULL) {break;}if (word[0]=='\0') {continue;}insert(word);}}/* free(linebuf); */do_travel(&root);exit(0); }

在給一個例子：

#define MAX_NUM 26 enum NODE_TYPE{ //"COMPLETED" means a string is generated so far.COMPLETED,UNCOMPLETED }; struct Node {enum NODE_TYPE type;char ch;struct Node* child[MAX_NUM]; //26-tree->a, b ,c, .....z };struct Node* ROOT; //tree rootstruct Node* createNewNode(char ch){// create a new nodestruct Node *new_node = (struct Node*)malloc(sizeof(struct Node));new_node->ch = ch;new_node->type == UNCOMPLETED;int i;for(i = 0; i < MAX_NUM; i++)new_node->child[i] = NULL;return new_node; }void initialization() { //intiazation: creat an empty tree, with only a ROOT ROOT = createNewNode(' '); }int charToindex(char ch) { //a "char" maps to an index<br> return ch - 'a'; }int find(const char chars[], int len) {struct Node* ptr = ROOT;int i = 0;while(i < len) {if(ptr->child[charToindex(chars[i])] == NULL) {break;}ptr = ptr->child[charToindex(chars[i])];i++;}return (i == len) && (ptr->type == COMPLETED); }void insert(const char chars[], int len) {struct Node* ptr = ROOT;int i;for(i = 0; i < len; i++) {if(ptr->child[charToindex(chars[i])] == NULL) {ptr->child[charToindex(chars[i])] = createNewNode(chars[i]);}ptr = ptr->child[charToindex(chars[i])]; }ptr->type = COMPLETED; }

Trie樹的基本實現

字母樹的插入（Insert）、刪除（ Delete）和查找（Find）都非常簡單，用一個一重循環即可，即第i 次循環找到前i 個字母所對應的子樹，然后進行相應的操作。實現這棵字母樹，我們用最常見的數組保存（靜態開辟內存）即可，當然也可以開動態的指針類型（動態開辟內存）。至于結點對兒子的指向，一般有三種方法：

1、對每個結點開一個字母集大小的數組，對應的下標是兒子所表示的字母，內容則是這個兒子對應在大數組上的位置，即標號；

2、對每個結點掛一個鏈表，按一定順序記錄每個兒子是誰；

3、使用左兒子右兄弟表示法記錄這棵樹。

三種方法，各有特點。第一種易實現，但實際的空間要求較大；第二種，較易實現，空間要求相對較小，但比較費時；第三種，空間要求最小，但相對費時且不易寫。

3、 Trie樹的高級實現

可以采用雙數組（Double-Array）實現。利用雙數組可以大大減小內存使用量，具體實現細節見參考資料（5）（6）。

4、 Trie樹的應用

Trie是一種非常簡單高效的數據結構，但有大量的應用實例。

（1） 字符串檢索

事先將已知的一些字符串（字典）的有關信息保存到trie樹里，查找另外一些未知字符串是否出現過或者出現頻率。

舉例：

@? 給出N 個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現的順序寫出所有不在熟詞表中的生詞。

@? 給出一個詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有不良單詞。

（2）字符串最長公共前綴

Trie樹利用多個字符串的公共前綴來節省存儲空間，反之，當我們把大量字符串存儲到一棵trie樹上時，我們可以快速得到某些字符串的公共前綴。

舉例：

@ 給出N 個小寫英文字母串，以及Q 個詢問，即詢問某兩個串的最長公共前綴的長度是多少？

解決方案：首先對所有的串建立其對應的字母樹。此時發現，對于兩個串的最長公共前綴的長度即它們所在結點的公共祖先個數，于是，問題就轉化為了離線（Offline）的最近公共祖先（Least Common Ancestor，簡稱LCA）問題。

而最近公共祖先問題同樣是一個經典問題，可以用下面幾種方法：

1. 利用并查集（Disjoint Set），可以采用采用經典的Tarjan 算法；

2. 求出字母樹的歐拉序列（Euler Sequence ）后，就可以轉為經典的最小值查詢（Range Minimum Query，簡稱RMQ）問題了；

（關于并查集，Tarjan算法，RMQ問題，網上有很多資料。）

（3）排序

Trie樹是一棵多叉樹，只要先序遍歷整棵樹，輸出相應的字符串便是按字典序排序的結果。

舉例：

@ 給你N 個互不相同的僅由一個單詞構成的英文名，讓你將它們按字典序從小到大排序輸出。

（4） 作為其他數據結構和算法的輔助結構

如后綴樹，AC自動機等

5、 Trie樹復雜度分析

（1） 插入、查找的時間復雜度均為O(N)，其中N為字符串長度。

（2） 空間復雜度是26^n級別的，非常龐大（可采用雙數組實現改善）。

6、 總結

Trie樹是一種非常重要的數據結構，它在信息檢索，字符串匹配等領域有廣泛的應用，同時，它也是很多算法和復雜數據結構的基礎，如后綴樹，AC自動機等，因此，掌握Trie樹這種數據結構，對于一名IT人員，顯得非常基礎且必要！

7、 參考資料

（1）wiki：http://en.wikipedia.org/wiki/Trie

（2） 博文《字典樹的簡介及實現》：

http://hi.baidu.com/luyade1987/blog/item/2667811631106657f2de320a.html

（3） 論文《淺析字母樹在信息學競賽中的應用》

（4）? 論文《Trie圖的構建、活用與改進》

（5）? 博文《An Implementation of Double-Array Trie》：

http://linux.thai.net/~thep/datrie/datrie.html

（6） 論文《An Efficient Implementation of Trie Structures》：

http://www.google.com.hk/url?sa=t&source=web&cd=4&ved=0CDEQFjAD&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.14.8665%26rep%3Drep1%26type%3Dpdf&ei=qaehTZiyJ4u3cYuR_O4B&usg=AFQjCNF5icQbRO8_WKRd5lMh-eWFIty_fQ&sig2=xfqSGYHBKqOLXjdONIQNVw

7）剛剛分享了："算法合集之《淺析字母樹在信息學競賽中的應用》.pdf" 下載鏈接：http://t.cn/zOlasAH?http://t.cn/zOlasAQ

總結

以上是生活随笔為你收集整理的字典树（Trie tree）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。