字典樹，不就有點不一樣的一顆樹
本文轉載自微信公眾號「bigsai」，作者bigsai。轉載本文請聯系bigsai公眾號。
什么是字典樹
字典樹，是一種空間換時間的數據結構，又稱Trie樹、前綴樹，是一種樹形結構(字典樹是一種數據結構)，典型用于統計、排序、和保存大量字符串。所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
可能大部分情況你很難直觀或者有接觸的體驗，可能對前綴這個玩意沒啥概念，可能做題遇到前綴問題也是暴力匹配蒙混過關，如果字符串比較少使用哈希表等結構可能也能蒙混過關，但如果字符串比較長、相同前綴較多那么使用字典樹可以大大減少內存的使用和效率。一個字典樹的應用場景：在搜索框輸入部分單詞下面會有一些神關聯的搜索內容，你有時候都很神奇是怎么做到的，這其實就是字典樹的一個思想。
圖片真假可自行驗證
對于字典樹，有三個重要性質：
1：根節點不包含字符，除了根節點每個節點都只包含一個字符。root節點不含字符這樣做的目的是為了能夠包括所有字符串。
2：從根節點到某一個節點，路過字符串起來就是該節點對應的字符串。
3：每個節點的子節點字符不同，也就是找到對應單詞、字符是唯一的。
一個字典樹
設計實現字典樹
上面已經介紹了什么是字典樹，那么我們開始設計一個字典樹吧!
對于字典樹，可能不同的場景或者需求設計上有一些細致的區別，但整體來說一般的字典樹有插入、查詢(指定字符串)、查詢(前綴)。
我們首先來分析一下簡單情況吧，就是字符串中全部是26個小寫字母，剛好力扣208實現Trie樹可以作為一個實現的模板。
實現 Trie 類：
- Trie() 初始化前綴樹對象。
- void insert(String word) 向前綴樹中插入字符串 word 。
- boolean search(String word) 如果字符串 word 在前綴樹中，返回 true(即，在檢索之前已經插入);否則，返回 false 。
- boolean startsWith(String prefix) 如果之前已經插入的字符串 word 的前綴之一為 prefix ，返回 true ;否則，返回 false 。
怎么設計這個字典樹呢?
對于一個字典樹Trie類，肯定是要有一個根節點root的，而這個節點類型TrieNode也有很多設計方式，在這里我們為了簡單放一個26個大小的TrieNode類型數組，分別對應'a'-'z'的字符，同時用一個boolean類型變量isEnd表示是否為字符串末尾結束(如果為true說明)。
- class TrieNode {
- TrieNode son[];
- boolean isEnd;//結束標志
- public TrieNode()//初始化
- {
- son=new TrieNode[26];
- }
- }
用數組的話如果字符比較多的話可能會消耗一些內存空間，但是這里26個連續字符還好的，如果向一個字典樹中添加big,bit,bz 那么它其實是這樣的：
那么再分析一下具體操作：
插入操作：遍歷字符串，同時從字典樹root節點開始遍歷，找到每個字符對應的位置首先判斷是否為空，如果為空需要創建一個新的Trie。比如插入big的枚舉第一個b時候創建TrieNode,后面也是同理。不過重要的是要在停止的那個TrieNode將isEnd設為true表明這個節點是構成字符串的末尾節點。
這部分對應的關鍵代碼為：
- TrieNode root;
- /** 初始化 */
- public Trie() {
- root=new TrieNode();
- }
- /** Inserts a word into the trie. */
- public void insert(String word) {
- TrieNode node=root;//臨時節點用來枚舉
- for(int i=0;i<word.length();i++)//枚舉字符串
- {
- int index=word.charAt(i)-'a';//找到26個對應位置
- if(node.son[index]==null)//如果為空需要創建
- {
- node.son[index]=new TrieNode();
- }
- node=node.son[index];
- }
- node.isEnd=true;//最后一個節點
- }
查詢操作：查詢是建立在字典樹已經建好的情況下，這個過程和查詢有些類似但不需要創建TrieNode，如果枚舉的過程一旦發現該TrieNode未被初始化(即為空)則返回false，如果順利到最后看看該節點的isEnd是否為true(是否已插入已改字符結尾的字符串)，如果為true則返回true。
這里用一個例子可能更好懂。插入big串，如果查找ba會因為第二次a對應TrieNode為null為為空。如果查找bi也會返回失敗，因為之前插入的big只在g字符對應TrieNode標識isEnd=true，但i字符下面的isEnd為false，即不存在bi字符串。
該部分對應的核心代碼為：
- public boolean search(String word) {
- TrieNode node=root;
- for(int i=0;i<word.length();i++)
- {
- int index=word.charAt(i)-'a';
- if(node.son[index]==null)//為null直接返回false
- {
- return false;
- }
- node=node.son[index];
- }
- return node.isEnd==true;
- }
前綴查找：和查詢很相似但是有點區別，查找失敗的話返回false，但是如果能進行到最后一步那么返回true。上面例子插入big查找bi同樣返回true，因為存在以它為前綴的字符串。
該對應對應的核心代碼為：
- public boolean startsWith(String prefix) {
- TrieNode node=root;
- for(int i=0;i<prefix.length();i++)
- {
- int index=prefix.charAt(i)-'a';
- if(node.son[index]==null)
- {
- return false;
- }
- node=node.son[index];
- }
- //能執行到最后即返回true
- return true;
- }
上面代碼合在一起就是完整的字典樹了，最基礎的版本。完整版為：
代碼
字典樹小思考
字典樹基礎班很容易，但很可能會出現一些延伸。
對于上面是26個字符的，我們很容易用ASCII找到對應索引，如果字符可能性比較多，用數組可能浪費的空間比較大，那我們也可以用HashMap或者List來存儲元素啊，用List的話就需要順序枚舉，用HashMap就可以直接查詢，這里就講解一個使用HashMap()實現的字典樹。
使用HashMap替代數組(不過使用哈希就不自帶排序功能了)，其實邏輯是一樣的，只需要判斷時候用HashMap判斷是否存在對應的key即可，HashMap的類型為：
Map
使用HashMap實現的字典樹完整代碼為：
- import java.util.HashMap;
- import java.util.Map;
- public class Trie{
- class TrieNode{
- Map<Character,TrieNode> sonMap;
- boolean idEnd;
- public TrieNode()
- {
- sonMap=new HashMap<>();
- }
- }
- TrieNode root;
- public Trie()
- {
- root=new TrieNode();
- }
- public void insert(String word) {
- TrieNode node=root;
- for(int i=0;i<word.length();i++)
- {
- char ch=word.charAt(i);
- if(!node.sonMap.containsKey(ch))//不存在插入
- {
- node.sonMap.put(ch,new TrieNode());
- }
- node=node.sonMap.get(ch);
- }
- node.idEnd=true;
- }
- public boolean search(String word) {
- TrieNode node=root;
- for(int i=0;i<word.length();i++)
- {
- char ch=word.charAt(i);
- if(!node.sonMap.containsKey(ch))
- {
- return false;
- }
- node=node.sonMap.get(ch);
- }
- return node.idEnd==true;//必須標記為true證明有該字符串
- }
- public boolean startsWith(String prefix) {
- TrieNode node=root;
- for(int i=0;i<prefix.length();i++)
- {
- char ch=prefix.charAt(i);
- if(!node.sonMap.containsKey(ch))
- {
- return false;
- }
- node=node.sonMap.get(ch);
- }
- return true;//執行到最后一步即可
- }
- }
前面講了，字典樹用于大量字符的統計、排序、儲存，其實排序就是和采用數組的方式可以進行排序，因為字符的ASCII有序，在讀取時候可以按照這個規則讀取，這個思想就和基數排序有點像了。
而統計的話可能會面臨數量上統計，可能是出現過次數或者前綴單詞數量統計，如果每次都枚舉可能有點浪費時間，但你可以TrieNode中添加一個變量，每次插入的時候可以統計次數。如果字符串有重復那可以直接添加，如果字符串要去重那可以確定插入成功再給路徑上前綴單詞總數分別自增。這個的話就要具體問題具體分析了。
此外，字典樹還有一個在ACM中用于解決求異或最值的問題，我們稱之為：01字典樹，大家感興趣也可以自行了解(后面可能會介紹)。
總結
通過本文，想必你對字典樹有了一個較好的認識，本篇的話目的還是在于讓讀者能夠認識和學會基礎的字典樹，對其它變形優化能有個初步的認識。
字典樹可以最大限度地減少無謂的字符串比較，用于詞頻統計和大量字符串排序。自帶排序功能，使用中序遍歷序列即可得到排序序列。但是如果字符很多相同前綴很少的話那字典樹就沒啥效率優勢的(因為要一個一個訪問節點)。
字典樹的真實應用有很多，例如字符串檢索、文本預測、自動完成，see also，拼寫檢查、詞頻統計、排序、字符串最長公共前綴、字符串搜索的前綴匹配、作為其他數據結構和算法的輔助結構等等，這里就不再介紹啦。
