一、定義

Trie樹，又稱為前綴樹（Prefix Tree）、單詞查找樹或鍵樹，是一種多叉樹結(jié)構(gòu)。

二、基本性質(zhì)

• 根節(jié)點不包含字符，除根節(jié)點外的每一個子節(jié)點都包含一個字符。
• 從根節(jié)點到某一個節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。
• 每個節(jié)點的所有子節(jié)點包含的字符互不相同。

三、代碼

#include <iostream>#include <string>using namespace std;#define ALPHABET_SIZE 26typedef struct trie_node {int count; // 記錄該節(jié)點代表的單詞的個數(shù)trie_node *children[ALPHABET_SIZE]; // 各個子節(jié)點 }*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; }/*** 查詢：不存在返回0，存在返回出現(xiàn)的次數(shù)*/ 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;elsereturn node->count; }int main() {// 關(guān)鍵字集合char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};trie root = create_trie_node();// 創(chuàng)建trie樹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; }

四、優(yōu)缺點

優(yōu)點

1、插入和查詢的效率很高，均是O（m），其中 m 是待插入/查詢的 字符串長度 。

2、關(guān)于查詢，有人會說hash表時間復(fù)雜度是O（1）不是更快？但是哈希搜索的效率取決于哈希函數(shù)的好壞，若一個壞的hash函數(shù)導(dǎo)致了很多沖突，效率不一定比Trie樹高。

3、Trie樹中不同的關(guān)鍵字不會產(chǎn)生沖突。

4、Trie樹中只有在允許一個關(guān)鍵字關(guān)聯(lián)多個值的情況下才有類似hash碰撞發(fā)生。

5、Trie樹不用求hash值，對短字符串有更快的速度。通常，求hash值也是需要遍歷字符串的(與hash函數(shù)相關(guān))。

Trie樹可以對關(guān)鍵字 按照字典序排序 （先序遍歷）。

字典排序（lexicographical order）是一種對于隨機變量形成序列的排序方法。其方法是，按照字母順序，或者數(shù)字小大順序，由小到大的形成序列。

6、每一顆Trie樹都可以被看做一個簡單版的確定有限狀態(tài)的自動機（DFA，deterministic finite automation），也就是說，對于一個任意給定屬于該自動機的狀態(tài)（①）和一個屬于該自動機字母表的字符（②），都可以根據(jù)給定的轉(zhuǎn)移函數(shù)（③）轉(zhuǎn)到下一個狀態(tài)。其中：

① 對于Trie樹的每一個節(jié)點都確定一個自動機的狀態(tài)。

② 給定一個屬于該自動機字母表的字符，在圖中可以看到根據(jù)不同字符形成的分支；

③ 從當(dāng)前節(jié)點進入下一層次節(jié)點的過程進過狀態(tài)轉(zhuǎn)移函數(shù)得出。
核心思想是：空間換時間，利用字符串的公共前綴來減少無謂的字符串比較以達到提高查詢效率的目的。

缺點

當(dāng)hash函數(shù)很好時，Trie樹的查找效率低于哈希搜索。

空間消耗大。

五、應(yīng)用

1、字符串檢索

檢索、查詢功能是Trie樹最原始功能，思路就是從根節(jié)點開始一個一個字符進行比較。

如果沿路比較，發(fā)現(xiàn)不同的字符，則表示該字符串在集合中不存在。

如果所有的字符全部比較并且完全相同，還需要判斷最后一個節(jié)點標(biāo)識位（標(biāo)記該節(jié)點是否為一個關(guān)鍵字）。

2、詞頻統(tǒng)計?

Trie樹常被搜索引擎用于文本詞頻統(tǒng)計。

思路：為了實現(xiàn)詞頻統(tǒng)計，我們修改了節(jié)點結(jié)構(gòu)，用一個整型變量count來計數(shù)。對每一個關(guān)鍵字執(zhí)行插入操作，若已存在，計數(shù)加1，若不存在，插入后count置 1。?
(1. 2. 都可以用hash table做)

3、字符串排序?

Trie樹可以對大量字符串按字典序進行排序，思路也很簡單：遍歷一次所有關(guān)鍵字，將它們?nèi)坎迦雝rie樹，樹的每個結(jié)點的所有兒子很顯然地按照字母表排序，然后先序遍歷輸出Trie樹中所有關(guān)鍵字即可。

4、前綴匹配?

例如：找出一個字符串集合中所有以ab開頭的字符串。我們只需要用所有字符串構(gòu)造一個trie樹，然后輸出以a->b->開頭的路徑上的關(guān)鍵字即可。 trie樹前綴匹配常用于搜索提示。如當(dāng)輸入一個網(wǎng)址，可以自動搜索出可能的選擇。當(dāng)沒有完全匹配的搜索結(jié)果，可以返回前綴最相似的可能。

5、作為輔助結(jié)構(gòu)?

如后綴樹，AC自動機?
有窮自動機 參考資料：http://blog.csdn.net/yukuninfoaxiom/article/details/6057736

6、與哈希表相比?

優(yōu)點：

trie數(shù)據(jù)查找與不完美哈希表（鏈表實現(xiàn)）在最壞情況下更快；對于trie樹，最差為O（m），m為查找字符串的長度；對于不完美哈希表，會有鍵值沖突（不同鍵哈希相同），最壞為O（N），N為全部字符產(chǎn)生的個數(shù)。典型情況是O（m）用于哈希計算，O（1）用于數(shù)據(jù)查找。

trie中不同鍵沒有沖突

trie的桶與哈希表用于存儲鍵沖突的桶類似，僅在單個鍵與多個值關(guān)聯(lián)時需要

當(dāng)更多的鍵加入到trie中，無需提供hash方法或改變hash方法

trie通過鍵為條目提供字母順序?

缺點：

trie數(shù)據(jù)查找在某些情況下（磁盤或隨機訪問時間遠遠高于主存）比哈希表慢

當(dāng)鍵值為某些類型（如浮點型），前綴鏈很長且前綴不是特別有意義。

一些trie會比hash表更消耗內(nèi)存。對于trie，每個字符串的每個字符都要分配內(nèi)存；對于大多數(shù)hash，只需要為整個條目分配一塊內(nèi)存。

7、與二叉搜索樹相比

二叉搜索樹，又稱二叉排序樹，它滿足：

任意節(jié)點如果左子樹不為空，左子樹所有節(jié)點的值都小于根節(jié)點的值；

任意節(jié)點如果右子樹不為空，右子樹所有節(jié)點的值都大于根節(jié)點的值；

左右子樹也都是二叉搜索樹；

所有節(jié)點的值都不相同。

其實二叉搜索樹的優(yōu)勢已經(jīng)在與查找、插入的時間復(fù)雜度上了，通常只有O(log n)，很多集合都是通過它來實現(xiàn)的。在進行插入的時候，實質(zhì)上是給樹添加新的葉子節(jié)點，避免了節(jié)點移動，搜索、插入和刪除的復(fù)雜度等于樹的高度，屬于O(log n)，最壞情況下整棵樹所有的節(jié)點都只有一個子節(jié)點，完全變成一個線性表，復(fù)雜度是O(n)。

Trie樹在最壞情況下查找要快過二叉搜索樹，如果搜索字符串長度用m來表示的話，它只有O(m)，通常情況（樹的節(jié)點個數(shù)要遠大于搜索字符串的長度）下要遠小于O(n)。
?

六、改進

1、按位樹（Btiwise Trie）：原理上和普通Trie樹差不多，只不過普通Trie樹存儲的最小單位是字符，但是Bitwise Trie存放的是位而已。位數(shù)據(jù)的存取由CPU指令一次直接實現(xiàn)，對于二進制數(shù)據(jù)，它理論上要比普通Trie樹快。

2、節(jié)點壓縮

①分支壓縮： 對于穩(wěn)定的Trie樹，基本上都是查找和讀取的操作，完全可以把一些分支進行壓縮。例如，下圖中最右側(cè)分支inn可以直接壓縮成一個節(jié)點“inn”，而不需要作為一個常規(guī)子樹存在。Radix樹就是根據(jù)這個原理來解決Trie樹過深的問題。?

②節(jié)點映射表：這種方式也是Trie樹節(jié)點可能幾乎完全確定下采用的，針對Trie樹節(jié)點的每一個狀態(tài)，如果狀態(tài)總數(shù)重復(fù)很多的話，通過一個元素為數(shù)字的多維數(shù)組（比如Triple Array Trie）來表示，這樣存儲Trie樹本身的空間開銷會小一些，雖然引入了額外的映射表。

3、雙數(shù)組TRIE樹（Double Array Trie）

它在保證Trie樹檢索速度的前提下，提高空間利用率而提出的一種數(shù)據(jù)結(jié)構(gòu)，本質(zhì)上還是一個確定有限自動機。（所謂DFA就是一個能夠?qū)崿F(xiàn)狀態(tài)專一的自動機，對于一個給定的屬于該自動機的狀態(tài)和一個數(shù)據(jù)該自動機字符表Σ的字符，它能夠根據(jù)預(yù)先給定的狀態(tài)轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個狀態(tài)。）

對于DAT來說，每個節(jié)點代表自動機的一個狀態(tài)， 根據(jù)變量的不同，進行狀態(tài)轉(zhuǎn)移，當(dāng)達到結(jié)束狀態(tài)或者無法轉(zhuǎn)移時，完成查詢。

參考資料：http://blog.csdn.net/zzran/article/details/8462002

七、例題

http://acm.hdu.edu.cn/showproblem.php?pid=1251

http://acm.hdu.edu.cn/showproblem.php?pid=1671

八、參考文章

https://blog.csdn.net/hihozoo/article/details/51248823

http://www.raychase.net/1783?replytocom=264917

https://blog.csdn.net/v_july_v/article/details/6897097

http://www.cnblogs.com/tanky_woo/archive/2010/09/24/1833717.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。