Trie這個(gè)名字取自“retrieval”，檢索，因?yàn)門(mén)rie可以只用一個(gè)前綴便可以在一部字典中找到想要的單詞。

雖然發(fā)音與「Tree」一致，但為了將這種 字典樹(shù) 與 普通二叉樹(shù) 以示區(qū)別，程序員小吳一般讀「Trie」尾部會(huì)重讀一聲，可以理解為讀「TreeE」。

Trie 樹(shù)，也叫“字典樹(shù)”。顧名思義，它是一個(gè)樹(shù)形結(jié)構(gòu)。它是一種專門(mén)處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，用來(lái)解決在一組字符串集合中快速查找某個(gè)字符串的問(wèn)題。

此外 Trie 樹(shù)也稱前綴樹(shù)（因?yàn)槟彻?jié)點(diǎn)的后代存在共同的前綴，比如pan是panda的前綴）。

它的key都為字符串，能做到高效查詢和插入，時(shí)間復(fù)雜度為O(k)，k為字符串長(zhǎng)度，缺點(diǎn)是如果大量字符串沒(méi)有共同前綴時(shí)很耗內(nèi)存。

它的核心思想就是通過(guò)最大限度地減少無(wú)謂的字符串比較，使得查詢高效率，即「用空間換時(shí)間」，再利用共同前綴來(lái)提高查詢效率。

Trie樹(shù)的特點(diǎn)

假設(shè)有 5 個(gè)字符串，它們分別是：code，cook，five，file，fat?，F(xiàn)在需要在里面多次查找某個(gè)字符串是否存在。如果每次查找，都是拿要查找的字符串跟這 5 個(gè)字符串依次進(jìn)行字符串匹配，那效率就比較低，有沒(méi)有更高效的方法呢？

如果將這 5 個(gè)字符串組織成下圖的結(jié)構(gòu)，從肉眼上掃描過(guò)去感官上是不是比查找起來(lái)會(huì)更加迅速。

Trie樹(shù)樣子

通過(guò)上圖，可以發(fā)現(xiàn) Trie樹(shù) 的三個(gè)特點(diǎn)：

根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符

從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串

每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同

通過(guò)動(dòng)畫(huà)理解 Trie 樹(shù)構(gòu)造的過(guò)程。在構(gòu)造過(guò)程中的每一步，都相當(dāng)于往 Trie 樹(shù)中插入一個(gè)字符串。當(dāng)所有字符串都插入完成之后，Trie 樹(shù)就構(gòu)造好了。

Trie 樹(shù)構(gòu)造

Trie樹(shù)的插入操作

Trie樹(shù)的插入操作

Trie樹(shù)的插入操作很簡(jiǎn)單，其實(shí)就是將單詞的每個(gè)字母逐一插入 Trie樹(shù)。插入前先看字母對(duì)應(yīng)的節(jié)點(diǎn)是否存在，存在則共享該節(jié)點(diǎn)，不存在則創(chuàng)建對(duì)應(yīng)的節(jié)點(diǎn)。比如要插入新單詞cook，就有下面幾步：

插入第一個(gè)字母c，發(fā)現(xiàn)root節(jié)點(diǎn)下方存在子節(jié)點(diǎn)c，則共享節(jié)點(diǎn)c

插入第二個(gè)字母o，發(fā)現(xiàn)c節(jié)點(diǎn)下方存在子節(jié)點(diǎn)o，則共享節(jié)點(diǎn)o

插入第三個(gè)字母o，發(fā)現(xiàn)o節(jié)點(diǎn)下方不存在子節(jié)點(diǎn)o，則創(chuàng)建子節(jié)點(diǎn)o

插入第三個(gè)字母k，發(fā)現(xiàn)o節(jié)點(diǎn)下方不存在子節(jié)點(diǎn)k，則創(chuàng)建子節(jié)點(diǎn)k

至此，單詞cook中所有字母已被插入 Trie樹(shù) 中，然后設(shè)置節(jié)點(diǎn)k中的標(biāo)志位，標(biāo)記路徑 root->c->o->o->k 這條路徑上所有節(jié)點(diǎn)的字符可以組成一個(gè)單詞cook

Trie樹(shù)的查詢操作

在 Trie 樹(shù)中查找一個(gè)字符串的時(shí)候，比如查找字符串 code，可以將要查找的字符串分割成單個(gè)的字符 c，o，d，e，然后從 Trie 樹(shù)的根節(jié)點(diǎn)開(kāi)始匹配。如圖所示，綠色的路徑就是在 Trie 樹(shù)中匹配的路徑。

code的匹配路徑

如果要查找的是字符串 cod(鱈魚(yú))呢？還是可以用上面同樣的方法，從根節(jié)點(diǎn)開(kāi)始，沿著某條路徑來(lái)匹配，如圖所示，綠色的路徑，是字符串 cod 匹配的路徑。但是，路徑的最后一個(gè)節(jié)點(diǎn)「d」并不是橙色的，并不是單詞標(biāo)志位，所以 cod 字符串不存在。也就是說(shuō)，cod是某個(gè)字符串的前綴子串，但并不能完全匹配任何字符串。

cod的匹配路徑

程序員不要當(dāng)一條咸魚(yú)，要向 cook 靠攏：）

Trie樹(shù)的刪除操作

Trie樹(shù)的刪除操作與二叉樹(shù)的刪除操作有類似的地方，需要考慮刪除的節(jié)點(diǎn)所處的位置，這里分三種情況進(jìn)行分析：

刪除整個(gè)單詞（比如hi）

刪除整個(gè)單詞

從根節(jié)點(diǎn)開(kāi)始查找第一個(gè)字符h

找到h子節(jié)點(diǎn)后，繼續(xù)查找h的下一個(gè)子節(jié)點(diǎn)i

i是單詞hi的標(biāo)志位，將該標(biāo)志位去掉

i節(jié)點(diǎn)是hi的葉子節(jié)點(diǎn)，將其刪除

刪除后發(fā)現(xiàn)h節(jié)點(diǎn)為葉子節(jié)點(diǎn)，并且不是單詞標(biāo)志位，也將其刪除

這樣就完成了hi單詞的刪除操作

刪除前綴單詞（比如cod）

刪除前綴單詞

這種方式刪除比較簡(jiǎn)單。

只需要將cod單詞整個(gè)字符串查找完后，d節(jié)點(diǎn)因?yàn)椴皇侨~子節(jié)點(diǎn)，只需將其單詞標(biāo)志去掉即可。

刪除分支單詞（比如cook）

刪除分支單詞

與刪除整個(gè)單詞情況類似，區(qū)別點(diǎn)在于刪除到cook的第一個(gè)o時(shí)，該節(jié)點(diǎn)為非葉子節(jié)點(diǎn)，停止刪除，這樣就完成 cook 字符串的刪除操作。

Trie樹(shù)的應(yīng)用

事實(shí)上 Trie樹(shù) 在日常生活中的使用隨處可見(jiàn)，比如這個(gè)：

具體來(lái)說(shuō)就是經(jīng)常用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希表高。

1. 前綴匹配

例如：找出一個(gè)字符串集合中所有以 五分鐘 開(kāi)頭的字符串。我們只需要用所有字符串構(gòu)造一個(gè) trie樹(shù)，然后輸出以 五?>分?>鐘 開(kāi)頭的路徑上的關(guān)鍵字即可。

trie樹(shù)前綴匹配常用于搜索提示。如當(dāng)輸入一個(gè)網(wǎng)址，可以自動(dòng)搜索出可能的選擇。當(dāng)沒(méi)有完全匹配的搜索結(jié)果，可以返回前綴最相似的可能。

google搜索

2. 字符串檢索

給出 N 個(gè)單詞組成的熟詞表，以及一篇全用小寫(xiě)英文書(shū)寫(xiě)的文章，按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞。

檢索/查詢功能是Trie樹(shù)最原始的功能。給定一組字符串，查找某個(gè)字符串是否出現(xiàn)過(guò)，思路就是從根節(jié)點(diǎn)開(kāi)始一個(gè)一個(gè)字符進(jìn)行比較：

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

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

Trie樹(shù)的局限性

如前文所講，Trie的核心思想是空間換時(shí)間，利用字符串的公共前綴來(lái)降低查詢時(shí)間的開(kāi)銷以達(dá)到提高效率的目的。

假設(shè)字符的種數(shù)有 m 個(gè)，有若干個(gè)長(zhǎng)度為n的字符串構(gòu)成了一個(gè) Trie 樹(shù) ，則每個(gè)節(jié)點(diǎn)的出度為 m（即每個(gè)節(jié)點(diǎn)的可能子節(jié)點(diǎn)數(shù)量為 m），Trie 樹(shù)的高度為 n。很明顯我們浪費(fèi)了大量的空間來(lái)存儲(chǔ)字符，此時(shí) Trie 樹(shù)的最壞空間復(fù)雜度為 O(m^n)。也正由于每個(gè)節(jié)點(diǎn)的出度為 m，所以我們能夠沿著樹(shù)的一個(gè)個(gè)分支高效的向下逐個(gè)字符的查詢，而不是遍歷所有的字符串來(lái)查詢，此時(shí) Trie 樹(shù)的最壞時(shí)間復(fù)雜度為 O(n)。

這正是空間換時(shí)間的體現(xiàn)，也是利用公共前綴降低查詢時(shí)間開(kāi)銷的體現(xiàn)。