字典樹(shù)（Trie）可以保存一些字符串->值的對(duì)應(yīng)關(guān)系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不過(guò) Trie 的 key 只能是字符串。
Trie 的強(qiáng)大之處就在于它的時(shí)間復(fù)雜度。它的插入和查詢(xún)時(shí)間復(fù)雜度都為 O(k) ，其中 k 為 key 的長(zhǎng)度，與 Trie 中保存了多少個(gè)元素?zé)o關(guān)。Hash 表號(hào)稱(chēng)是 O(1) 的，但在計(jì)算 hash 的時(shí)候就肯定會(huì)是 O(k) ，而且還有碰撞之類(lèi)的問(wèn)題；Trie 的缺點(diǎn)是空間消耗很高。
至于Trie樹(shù)的實(shí)現(xiàn)，可以用數(shù)組，也可以用指針動(dòng)態(tài)分配，我做題時(shí)為了方便就用了數(shù)組，靜態(tài)分配空間。
Trie樹(shù)，又稱(chēng)單詞查找樹(shù)或鍵樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：最大限度地減少無(wú)謂的字符串比較，查詢(xún)效率比哈希表高。
Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來(lái)降低查詢(xún)時(shí)間的開(kāi)銷(xiāo)以達(dá)到提高效率的目的。
Trie樹(shù)中每個(gè)單詞都是通過(guò)character by character方法進(jìn)行存儲(chǔ)，相同前綴單詞共享前綴節(jié)點(diǎn).
可以看到,每條路徑組成一個(gè)單詞.上面這顆樹(shù)存了to/tea/ted/ten/inn這些詞.

Trie樹(shù)的基本性質(zhì)可以歸納為：
（1）根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)意外每個(gè)節(jié)點(diǎn)只包含一個(gè)字符。
（2）從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
（3）每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符串不相同。

性質(zhì)
（1）根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)只包含一個(gè)字符。
（2）從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
（3）每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符串不相同。

基本思想（以字母樹(shù)為例）：
1、插入過(guò)程
對(duì)于一個(gè)單詞，從根開(kāi)始，沿著單詞的各個(gè)字母所對(duì)應(yīng)的樹(shù)中的節(jié)點(diǎn)分支向下走，直到單詞遍歷完，將最后的節(jié)點(diǎn)標(biāo)記為紅色，表示該單詞已插入Trie樹(shù)。
2、查詢(xún)過(guò)程
同樣的，從根開(kāi)始按照單詞的字母順序向下遍歷trie樹(shù)，一旦發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)標(biāo)記不存在或者單詞遍歷完成而最后的節(jié)點(diǎn)未標(biāo)記為紅色，則表示該單詞不存在，若最后的節(jié)點(diǎn)標(biāo)記為紅色，表示該單詞存在。

應(yīng)用
（1）詞頻統(tǒng)計(jì)
比直接用hash節(jié)省空間
（2）搜索提示
輸入前綴的時(shí)候提示可以構(gòu)成的詞
（3）作為輔助結(jié)構(gòu)
如后綴樹(shù)，AC自動(dòng)機(jī)等的輔助結(jié)構(gòu)

實(shí)現(xiàn)
雖然Python沒(méi)有指針,但是可以用嵌套字典來(lái)實(shí)現(xiàn)樹(shù)結(jié)構(gòu).對(duì)于非ascii的單詞,統(tǒng)一用unicode編碼來(lái)插入與搜索.

#coding=utf-8 class Trie:   root = {}   END = '/'   def add(self, word):     #從根節(jié)點(diǎn)遍歷單詞,char by char,如果不存在則新增,最后加上一個(gè)單詞結(jié)束標(biāo)志     node = self.root     for c in word:       node=node.setdefault(c,{})     node[self.END] = None    def find(self, word):     node = self.root     for c in word:       if c not in node:         return False       node = node[c]     return self.END in node