本文內(nèi)容主要來源：http://www.cnblogs.com/konrad/p/7746030.html
? ? ? ?一、基本概念
? ? ? ? Trie 樹又稱字典樹、單詞查找樹、前綴樹等，是一種樹形結(jié)構(gòu)。典型應用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計等。
? ? ? ?優(yōu)點：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比較高。
? ? ? ?缺點：基于空間換時間的思想，所以系統(tǒng)中若存在大量的沒有公共前綴的字符串則會消耗大量內(nèi)存。
? ? ? ?核心思想：空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
? ? ? ?三個特性：
? ? ? ?1. 根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符。
? ? ? ?2. 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應的字符串。
? ? ? ?3. 每個節(jié)點的所有子節(jié)點包含的字符都不相同。
? ? ? ?例：and, as, at, cn, com構(gòu)建的 Trie 樹如下：
? ? ? ?二、Trie 樹的基本操作
? ? ? ?假設存在字符串 str，Trie樹的根結(jié)點為 root，i=0，p=root
? ? ? ?1. 插入
? ? ? ?1) 取 str[i]，判斷 p->next[str[i]-'a'] 是否為空，若為空，則建立結(jié)點 temp，并將 p->next[str[i]-‘a(chǎn)’] 指向 temp，然后 p 指向 temp；若不為空，則 p=p->next[str[i]-'a']；
? ? ? ?2) i++，繼續(xù)取 str[i]，循環(huán)1) 中的操作，直到遇到結(jié)束符 '\0'，此時將當前結(jié)點 p 中的 isStr 置為 true，表示從根節(jié)點到當前節(jié)點這條路徑上的字符組成的字符串是一個詞。
? ? ? ?2. 查找
? ? ? ?1) 取 str[i]，判斷判斷 p->next[str[i]-‘a(chǎn)’] 是否為空，若為空，則返回 false；若不為空，則 p=p->next[str[i]-'a']，繼續(xù)取字符。
? ? ? ?2) 重復1)中的操作直到遇到結(jié)束符 '\0',若當前結(jié)點 p 不為空并且 isStr 為 true，則返回 true，否則返回 false。
? ? ? ?3. 刪除
? ? ? ?可以遞歸刪除整棵樹
三、Trie 樹的復雜度
? ? ? ?1. 插入、查找的時間復雜度均為 O(N)， N為字符串的長度。
? ? ? ?2. 英文字符為例，空間復雜度是 26^n, 可采用<雙數(shù)組實現(xiàn)>來改善。
四、Trie 樹的應用場景
? ? ? ?1. 字符串檢索、詞頻統(tǒng)計
? ? ? ?將已知的一些字符串（字典）的有關(guān)信息實現(xiàn)保存到 trie 樹里，查找另外一些未知字符串是否出現(xiàn)過或者出現(xiàn)頻率。
? ? ? ?2. 字符串最長公共前綴
? ? ? ?Trie 樹利用多個字符串的公共前綴來節(jié)省存儲空間，反之，當我們把大量字符串存儲到一棵 trie 樹上時，我們可以快速得到某些字符串的公共前綴。
? ? ? ?3. 排序
? ? ? ?只要先序遍歷整棵樹，輸出相應的字符串便是按字典排序的結(jié)果。
上一篇：python3 通過 pymysql 操作 mysql 數(shù)據(jù)庫
下一篇：Trie 樹（二）：java 簡單實現(xiàn)
