### Trie樹定義 Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。它有3個基本性質： (1)?????根節點不包含字符，除根節點外每一個節點都只包含一個字符。 (2)?????從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。 (3)?????每個節點的所有子節點包含的字符都不相同。 ### 樹的構建 **題目：**給你100000個長度不超過10的單詞。對于每一個單詞，我們要判斷他出沒出現過，如果出現了，求第一次出現在第幾個位置。**** **分析：**這題當然可以用hash來解決，但是本文重點介紹的是trie樹，因為在某些方面它的用途更大。比如說對于某一個單詞，我們要詢問它的前綴是否出現過。這樣hash就不好搞了，而用trie還是很簡單。假設我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開頭的我顯然不必考慮。而只要找以a開頭的中是否存在abcd就可以了。同樣的，在以a開頭中的單詞中，我們只要考慮以b作為第二個字母的，一次次縮小范圍和提高針對性，這樣一個樹的模型就漸漸清晰了。好比假設有b，abc，abd，bcd，abcd，efg，hii 這6個單詞，我們構建的樹就是如下圖這樣的：  對于一個單詞，只要順著根走到對應的節點，再看這個節點是否被標記為紅色就可以知道它是否出現過了。把這個節點標記為紅色，就相當于插入了這個單詞。這樣一來查詢和插入可以一起完成（重點體會這個查詢和插入是如何一起完成的），所用時間僅僅為單詞長度，在本題中因為每個單詞的長度不超過10。可以看到，trie樹每一層的節點數是26^i(i為層數)級別的。所以為了節省空間。我們用動態鏈表，或者用數組來模擬動態。空間的花費，不會超過單詞數×單詞長度。 ### 前綴查詢 上文中提到”比如說對于某一個單詞，我們要詢問它的前綴是否出現過。這樣hash就不好搞了，而用trie還是很簡單“。下面，咱們來看看這個前綴查詢問題： 題目：已知n個由小寫字母構成的平均長度為10(len)的單詞,判斷其中是否存在某個串為另一個串的前綴子串 1)? 最容易想到的：即從字符串集中從頭往后搜，看每個字符串是否為字符串集中某個字符串的前綴，復雜度為O(n^2)。 2) 使用hash：我們用hash存下所有字符串的所有的前綴子串，建立存有子串hash的復雜度為O(n*len)，而查詢的復雜度為O(n)*O(1)= O(n)。**NOTE:**因為是前綴子串，所以一個長度為len的字符串的前綴子串數目為len **例如：**abc的前綴子串為a，ab，abc 3) 使用trie：因為當查詢如字符串abc是否為某個字符串的前綴時，顯然以b,c,d....等不是以a開頭的字符串就不用查找了。所以建立trie的復雜度為O(n*len)，而建立+查詢在trie中是可以同時執行的，建立的過程也就可以成為查詢的過程，hash就不能實現這個功能。所以總的復雜度為O(n*len)，實際查詢的復雜度也只是O(len)。（說白了，就是Trie樹的平均高度h為len，所以Trie樹的查詢復雜度為O（h）=O（len）。好比一棵二叉平衡樹的高度為logN，則其查詢，插入的平均時間復雜度亦為O（logN））。 下面解釋下上述方法3中所說的為什么hash不能將建立與查詢同時執行，而Trie樹卻可以：在hash中，例如現在要輸入兩個串911，911456，如果要同時查詢這兩個串，且查詢串的同時若hash中沒有則存入。那么，這個查詢與建立的過程就是先查詢其中一個串911，沒有，然后存入9、91、911；而后查詢第二個串911456，沒有然后存入9、91、911、9114、91145、911456。因為程序沒有記憶功能，所以并不知道911在輸入數據中出現過，只是照常以例行事，存入9、91、911、9114、911...。也就是說用hash必須先存入所有子串，然后for循環查詢。而trie樹中，存入911后，已經記錄911為出現的字符串，在存入911456的過程中就能發現而輸出答案；倒過來亦可以，先存入911456，在存入911時，當指針指向最后一個1時，程序會發現這個1已經存在，說明911必定是某個字符串的前綴。 ### 查詢 Trie樹是簡單但實用的數據結構，通常用于實現字典查詢。我們做即時響應用戶輸入的AJAX搜索框時，就是Trie開始。本質上，Trie是一顆存儲多個字符串的樹。相鄰節點間的邊代表一個字符，這樣樹的每條分支代表一則子串，而樹的葉節點則代表完整的字符串。和普通樹不同的地方是，相同的字符串前綴共享同一條分支。下面，再舉一個例子。給出一組單詞，inn, int, at, age,adv, ant, 我們可以得到下面的Trie：  搭建Trie的基本算法也很簡單，無非是逐一把每個單詞的每個字母插入Trie。插入前先看前綴是否存在。如果存在，就共享，否則創建對應的節點和邊。 比如要插入單詞add，就有下面幾步： (1)????? 考察前綴"a"，發現邊a已經存在。于是順著邊a走到節點a。 (2)????? 考察剩下的字符串"dd"的前綴"d"，發現從節點a出發，已經有邊d存在。于是順著邊d走到節點ad (3)????? 考察最后一個字符"d"，這下從節點ad出發沒有邊d了，于是創建節點ad的子節點add，并把邊ad->add標記為d ### Trie樹的應用 除了本文引言處所述的問題能應用Trie樹解決之外，Trie樹還能解決下述問題： 1) 有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。 2)一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析。 轉載請注明出處：[http://blog.csdn.net/utimes/article/details/8864150](http://blog.csdn.net/utimes/article/details/8864150)