作者 | 程式設計師小吳
責編 | 胡巍巍
Trie樹
Trie這個名字取自「retrieval」，檢索，因為Trie可以只用一個前綴便可以在一部字典中找到想要的單詞。
雖然發音與「Tree」一致，但為了將這種 字典樹 與 普通二叉樹 以示區別，程式設計師小吳一般讀「Trie」尾部會重讀一聲，可以理解為讀「TreeE」。
Trie樹，也叫「字典樹」。顧名思義，它是一個樹形結構。它是一種專門處理字符串匹配的數據結構，用來解決在一組字符串集合中快速查找某個字符串的問題。
此外Trie樹也稱前綴樹（因為某節點的後代存在共同的前綴，比如pan是panda的前綴）。
它的Key都為字符串，能做到高效查詢和插入，時間複雜度為O(k)，k為字符串長度，缺點是如果大量字符串沒有共同前綴時很耗內存。
它的核心思想就是通過最大限度地減少無謂的字符串比較，使得查詢高效率，即「用空間換時間」，再利用共同前綴來提高查詢效率。
Trie樹的特點
假設有5個字符串，它們分別是：Code，Cook，Five，File，Fat。現在需要在裡面多次查找某個字符串是否存在。如果每次查找，都是拿要查找的字符串跟這5個字符串依次進行字符串匹配，那效率就比較低，有沒有更高效的方法呢？
如果將這5個字符串組織成下圖的結構，從肉眼上掃描過去感官上是不是比查找起來會更加迅速。
Trie樹樣子
通過上圖，可以發現Trie樹的三個特點：
通過動畫理解Trie樹構造的過程。在構造過程中的每一步，都相當於往Trie樹中插入一個字符串。當所有字符串都插入完成之後，Trie樹就構造好了。
Trie 樹構造
Trie樹的插入操作
Trie樹的插入操作
Trie樹的插入操作很簡單，其實就是將單詞的每個字母逐一插入Trie樹。插入前先看字母對應的節點是否存在，存在則共享該節點，不存在則創建對應的節點。比如要插入新單詞Cook，就有下面幾步：
插入第一個字母c，發現Root節點下方存在子節點c，則共享節點c。
插入第二個字母o，發現c節點下方存在子節點o，則共享節點o。
插入第三個字母o，發現o節點下方不存在子節點o，則創建子節點o。
插入第三個字母k，發現o節點下方不存在子節點k，則創建子節點k。
至此，單詞cook中所有字母已被插入Trie樹中，然後設置節點k中的標誌位，標記路徑root->c->o->o->k這條路徑上所有節點的字符可以組成一個單詞Cook。
Trie樹的查詢操作
在Trie樹中查找一個字符串的時候，比如查找字符串code，可以將要查找的字符串分割成單個的字符c，o，d，e，然後從Trie樹的根節點開始匹配。如圖所示，綠色的路徑就是在Trie樹中匹配的路徑。
code的匹配路徑
如果要查找的是字符串cod（鱈魚）呢？還是可以用上面同樣的方法，從根節點開始，沿著某條路徑來匹配，如圖所示，綠色的路徑，是字符串cod匹配的路徑。
但是，路徑的最後一個節點「d」並不是橙色的，並不是單詞標誌位，所以cod字符串不存在。也就是說，cod是某個字符串的前綴子串，但並不能完全匹配任何字符串。
cod的匹配路徑
程式設計師不要當一條鹹魚，要向 cook 靠攏：）。
Trie樹的刪除操作
Trie樹的刪除操作與二叉樹的刪除操作有類似的地方，需要考慮刪除的節點所處的位置，這裡分三種情況進行分析：
刪除整個單詞（比如hi）刪除整個單詞
刪除前綴單詞（比如cod）：刪除前綴單詞
這種方式刪除比較簡單。
只需要將cod單詞整個字符串查找完後，d節點因為不是葉子節點，只需將其單詞標誌去掉即可。
刪除分支單詞（比如cook）：刪除分支單詞
與 刪除整個單詞 情況類似，區別點在於刪除到cook的第一個o時，該節點為非葉子節點，停止刪除，這樣就完成cook。
Trie樹的應用
事實上Trie樹在日常生活中的使用隨處可見，比如這個：
具體來說就是經常用於統計和排序大量的字符串（但不僅限於字符串），所以經常被搜尋引擎系統用於文本詞頻統計。
它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
1. 前綴匹配例如：找出一個字符串集合中所有以五分鐘開頭的字符串。我們只需要用所有字符串構造一個Trie樹，然後輸出以 五−>分−>鍾 開頭的路徑上的關鍵字即可。
Trie樹前綴匹配常用於搜索提示。如當輸入一個網址，可以自動搜索出可能的選擇。當沒有完全匹配的搜索結果，可以返回前綴最相似的可能。
Google搜索
2. 字符串檢索給出N個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，按最早出現的順序寫出所有不在熟詞表中的生詞。
檢索/查詢功能是Trie樹最原始的功能。給定一組字符串，查找某個字符串是否出現過，思路就是從根節點開始一個一個字符進行比較：
Trie樹的局限性
如前文所講，Trie的核心思想是空間換時間，利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
假設字符的種數有m個，有若干個長度為n的字符串構成了一個Trie樹 ，則每個節點的出度為m（即每個節點的可能子節點數量為m），Trie樹的高度為n。
很明顯我們浪費了大量的空間來存儲字符，此時Trie樹的最壞空間複雜度為O(m^n)。
也正由於每個節點的出度為m，所以我們能夠沿著樹的一個個分支高效的向下逐個字符的查詢，而不是遍歷所有的字符串來查詢，此時Trie樹的最壞時間複雜度為O(n)。
這正是空間換時間的體現，也是利用公共前綴降低查詢時間開銷的體現。
作者簡介：作者程式設計師小吳，哈工大學渣，目前正在學算法，開源項目 「 LeetCodeAnimation 」5500star，GitHub Trending 榜連續一月第一。歡迎大家關注我的微信公眾號：五分鐘學算法，一起學習，一起進步！
聲明：本文為作者投稿，版權歸其個人所有。
【End】
熱 文 推 薦
☞ 「5G 將是一個徹底的失敗通信技術」
☞ 你還沒聽過 CynosDB 嗎？不來這場資料庫技術沙龍就要 OUT 了！
☞ 叫板蘋果谷歌，微軟將開發者應用分成上調至 95%
☞網際網路沒有春天
☞13 歲少女因幾行 JS 代碼被逮了！
☞雲漫圈 | 如何給女朋友解釋什麼是HTTP
☞這份「插件英雄榜Top20」才是Chrome的正確打開方式！
☞劇情反轉! 創始人去世事件再爆新料, 1.8億美元難道去了天堂？
☞沒有一個人，能躲過程式設計師的誘惑！
System.out.println("點個好看吧！");
console.log("點個好看吧！");
print("點個好看吧！");
printf("點個好看吧！\n");
cout << "點個好看吧！" << endl;
Console.WriteLine("點個好看吧！");
Response.Write("點個好看吧！");
alert("點個好看吧！")
echo "點個好看吧！"