（給算法愛好者加星標，修煉編程內功）
作者：神奕
blog.csdn.net/lisonglisonglisong/article/details/45584721
【前言】在計算機科學中，trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。讓我們一起來學習下它吧。
一、什麼是Trie樹Trie樹，又叫字典樹、前綴樹（Prefix Tree）、單詞查找樹 或 鍵樹，是一種多叉樹結構。
如下圖：
上圖是一棵Trie樹，表示了關鍵字集合{「a」, 「to」, 「tea」, 「ted」, 「ten」, 「i」, 「in」, 「inn」} 。從上圖可以歸納出Trie樹的基本性質：
通常在實現的時候，會在節點結構中設置一個標誌，用來標記該結點處是否構成一個單詞（關鍵字）。
可以看出，Trie樹的關鍵字一般都是字符串，而且Trie樹把每個關鍵字保存在一條路徑上，而不是一個結點中。
另外，兩個有公共前綴的關鍵字，在Trie樹中前綴部分的路徑相同，所以Trie樹又叫做前綴樹（Prefix Tree）。
二、Trie樹的優缺點Trie樹的核心思想是空間換時間，利用字符串的公共前綴來減少無謂的字符串比較以達到提高查詢效率的目的。
優點插入和查詢的效率很高，都為O(m)O(m)，其中 mm 是待插入/查詢的字符串的長度。
關於查詢，會有人說 hash 表時間複雜度是O(1)O(1)不是更快？但是，哈希搜索的效率通常取決於 hash 函數的好壞，若一個壞的 hash 函數導致很多的衝突，效率並不一定比Trie樹高。
Trie樹中不同的關鍵字不會產生衝突。
Trie樹只有在允許一個關鍵字關聯多個值的情況下才有類似hash碰撞發生。
Trie樹不用求 hash 值，對短字符串有更快的速度。通常，求hash值也是需要遍歷字符串的。
Trie樹可以對關鍵字按字典序排序。
缺點當 hash 函數很好時，Trie樹的查找效率會低於哈希搜索空間消耗比較大。三、Trie樹的應用1、字符串檢索檢索/查詢功能是Trie樹最原始的功能。思路就是從根節點開始一個一個字符進行比較：
struct trie_node{ bool isKey; trie_node *children[26]; };2、詞頻統計Trie樹常被搜尋引擎系統用於文本詞頻統計 。
struct trie_node{ int count; trie_node *children[26]; };思路：為了實現詞頻統計，我們修改了節點結構，用一個整型變量count來計數。對每一個關鍵字執行插入操作，若已存在，計數加1，若不存在，插入後count置1。
注意：第一、第二種應用也都可以用 hash table 來做。
3、字符串排序Trie樹可以對大量字符串按字典序進行排序，思路也很簡單：遍歷一次所有關鍵字，將它們全部插入trie樹，樹的每個結點的所有兒子很顯然地按照字母表排序，然後先序遍歷輸出Trie樹中所有關鍵字即可。
4、前綴匹配例如：找出一個字符串集合中所有以ab開頭的字符串。我們只需要用所有字符串構造一個trie樹，然後輸出以a->b->開頭的路徑上的關鍵字即可。
trie樹前綴匹配常用於搜索提示。如當輸入一個網址，可以自動搜索出可能的選擇。當沒有完全匹配的搜索結果，可以返回前綴最相似的可能。
5、作為其他數據結構和算法的輔助結構如後綴樹，AC自動機等。
四、Trie樹的實現
這裡為了方便，我們假設所有的關鍵字都由 a-z 的字母組成。
下面是 trie 樹的一種典型實現：
#include <iostream>#include <string>using namespace std;
#define ALPHABET_SIZE 26
typedef struct trie_node{ int count; trie_node *children[ALPHABET_SIZE]; }*trie;
trie_node* create_trie_node(){ trie_node* pNode = new trie_node(); pNode->count = 0; for(int i=0; i<ALPHABET_SIZE; ++i) pNode->children[i] = NULL; return pNode;}
void trie_insert(trie root, char* key){ trie_node* node = root; char* p = key; while(*p) { if(node->children[*p-'a'] == NULL) { node->children[*p-'a'] = create_trie_node(); } node = node->children[*p-'a']; ++p; } node->count += 1;}
int trie_search(trie root, char* key){ trie_node* node = root; char* p = key; while(*p && node!=NULL) { node = node->children[*p-'a']; ++p; }
if(node == NULL) return 0; else return node->count;}
int main(){ char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"}; trie root = create_trie_node();
for(int i = 0; i < 8; i++) trie_insert(root, keys[i]);
char s[][32] = {"Present in trie", "Not present in trie"}; printf("%s --- %s\n", "the", trie_search(root, "the")>0?s[0]:s[1]); printf("%s --- %s\n", "these", trie_search(root, "these")>0?s[0]:s[1]); printf("%s --- %s\n", "their", trie_search(root, "their")>0?s[0]:s[1]); printf("%s --- %s\n", "thaw", trie_search(root, "thaw")>0?s[0]:s[1]);
return 0;}對於Trie樹，我們一般只實現插入和搜索操作。這段代碼可以用來檢索單詞和統計詞頻。
- EOF -
覺得本文有幫助？請分享給更多人
推薦關注「算法愛好者」，修煉編程內功
點讚和在看就是最大的支持❤️