【資料結構】Trie Tree：字典樹（字首樹）的實作

字典樹又稱為字首樹或Trie樹，是處理字元串常見的資料結構。假設組成所有單詞的字元僅為a-z。

字典樹介紹

字典樹是一種樹形結構，優點是利用字元串的公共字首來節約存儲空間，比如加入"abc"、“abcd”、“abd”、“b”、“bcd”、“efg”、"hik"之後，字典樹如圖所示。

基本特性

• 根節點沒有字元路徑。除了根節點外，每一個節點都被一個字元路徑找到。
• 從根節點到某一節點，将路徑上經過的字元連接配接起來，為掃過的對應字元串。
• 每個節點向下所有的字元路徑上的字元都不同。

在字典樹上搜尋添加過的單詞步驟為：

1. 從根節點開始搜尋。
2. 取得要查找單詞的第一個字母，并根據該字母選擇對應的字元路徑向下繼續搜尋。
3. 字元路徑指向的第二層節點上，根據第二個字母選擇對應的字元路徑向下繼續搜尋。
4. 一直向下搜尋，如果單詞搜尋完後，找到的最後一個節點是一個終止節點，比如圖中的實心節點，說明字典樹中含有這個單詞，如果找到的最後一個節點不是一個終止節點，說明單詞不是字典樹中添加過的單詞。如果還沒搜尋完，但是已經沒有後續節點了，也說明單詞不是字典樹中添加過的單詞。

資料結構類型定義

public class TrieNode {
	public int path;
	public int end;
	public TrieNode[] map;

	public TrieNode() {
		path = 0;
		end = 0;
		map = new TrieNode[26];
	}
}
           

Variable	用途
path	表示有多少個單詞共用這個節點
end	表示有多少個單詞以這個節點結尾
map	實質為一個哈希表結構，key代表該節點的一條字元路徑，value表示字元路徑指向的節點

注：在字元類較多的情況下，可以選擇真實的哈希表結構實作map。

Trie樹實作

• void insert(String word)：假設word的長度為N，從左到右周遊word中的每一個字元，并以此從頭節點開始根據每一個word[i]，找到下一個節點。

  1）如果找的過程中節點不存在，就建立新節點，記為a，并令a.path=1。

  2）如果節點存在，記為b，令b.path++。

  3）通過最後一個字元(word[N-1])找到最後一個節點時記為e，令e.path++,e.paht++。

• boolean search(String word)：從左到右周遊word中每一個字元，并以此從頭節點開始根據每一個word[i]，找到下一個節點。

  1）如果找的過程中節點不存在，說明這個單詞的整個部分沒有添加到Trie樹中，否則不可能找的過程中節點不存在，直接傳回false。

  2）如果通過word[N-1]找到最後一個節點，記為e，如果e.end!=0，說明有單詞通過word[N-1]的字元路徑，并以節點e結尾，傳回true；如果e.end==0,傳回false；

• void delete(String word)：先調用search(word)，看word是否在Trie樹中；

  1）若不在，直接傳回；

  2）如在，從左到右周遊word中的每個字元，并依次從頭節點開始，根據每一個word[i]找到下一個的節點。在找的過程中，把掃過的每一個節點的path值減1。如果發現下一個節點的path值減完之後已經為0，直接從目前節點的map中删除後續的所有路徑，傳回即可。如果掃到最後一個節點，記為e，令e.path–,e.end–。

• int prefixNumber(String pre)：和search操作同理，根據pre不斷找到節點，假設最後的節點記為e，傳回e.path的值即可。

代碼實作

/**   
* @Title: Trie.java
* @Package com.hf.domain
* @Description: TODO
* @author hf寒沨  
* @date 2019年1月19日 下午2:51:50
* @version V1.0   
*/
package com.hf.domain;

/**
 * @ClassName: Trie
 * @Description:
 * @author hf寒沨
 * @date 2019年1月19日 下午2:51:50
 * 
 */
public class Trie {
	private TrieNode root;

	public Trie() {
		root = new TrieNode();
	}

	/**
	 * 
	* @Title: insert
	* @Description: insert word
	* @param @param word    
	* @return void   
	* @throws
	 */
	public void insert(String word) {
		if (word == null) {
			return;
		}
		char[] chs = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chs.length; i++) {
			index = chs[i] - 'a';
			if (node.map[index] == null) {
				node.map[index] = new TrieNode();
			}
			node = node.map[index];
			node.path++;
		}
		node.end++;
	}

	/**
	 * 
	* @Title: search
	* @Description: search word
	* @param @param word
	* @param @return    
	* @return boolean
	* @throws
	 */
	public boolean search(String word) {
		if (word == null) {
			return false;
		}
		char[] chs = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chs.length; i++) {
			index = chs[i] - 'a';
			if (node.map[index] == null) {
				return false;
			}
			node = node.map[index];
		}
		return node.end != 0;
	}

	/**
	 * 
	 * @Title: delete
	 * @Description: delete word from Trie Tree
	 * @param @param word   
	 * @return void    
	 * @throws
	 */
	public void delete(String word) {
		if (search(word)) {
			char[] chs = word.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a';
				if (node.map[index].path-- == 1) {
					node.map[index] = null;
					return;
				}
				node = node.map[index];
			}
			node.end--;
		}
	}

	/**
	 * 
	* @Title: prefixNumber
	* @Description: count the number of word with the common prefix
	* @param @param pre
	* @param @return     
	* @return int     
	* @throws
	 */
	public int prefixNumber(String pre) {
		if (pre == null) {
			return 0;
		}
		char[] chs = pre.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chs.length; i++) {
			index = chs[i] - 'a';
			if (node.map[index] == null) {
				return 0;
			}
			node = node.map[index];
		}
		return node.path;
	}

}

           

參考文獻

[1] 左程雲：程式員代碼面試指南