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

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

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

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

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

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

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

最新評論