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

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

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

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

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

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

#coding=utf-8 
class Trie: 
  root = {} 
  END = '/' 
  def add(self, word): 
    #從根節(jié)點(diǎn)遍歷單詞,char by char,如果不存在則新增,最后加上一個單詞結(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 

最新評論