Trie(字典樹、前綴樹)
什麼是Trie?
Trie是一個多叉樹，Trie專門為處理字符串而設計的。使用我們之前實現的二分搜索樹來查詢字典中的單詞，查詢的時間複雜度為O(logn),如果有100萬（220）個單詞，則logn大約等於20，但是使用Trie這種數據結構，查詢每個條目的時間複雜度，和一共有多少個條目無關！時間複雜度為O（w），w為被查詢單詞的長度！大多數單詞的長度小於10。
Trie將整個字符串以字母為單位，一個一個拆開，從根節點開始一直到葉子節點去遍歷，就形成了一個單詞，下圖中的Trie就存儲的四個單詞(cat,dog,deer,panda)
每個節點有26個字母指向下個節點的指針，考慮不同的語言，不同的情境，比如現在這個26個字符是沒有包含大寫字母的，如果需要包含大寫字母，則需要讓每個節點有52個指向下個節點的指針，如果現在要加入郵箱呢？所以這裡描述為每個節點有若干個指向下個節點的指針。
由於很多單詞可能是另外一個單詞的前綴，比如pan就是panda的前綴，那麼再Trie中如何存儲呢？所以我們應該對節點添加一個標識符，判斷該節點是否是某個單詞的結尾，某一個單詞的結尾只靠葉子節點是不能區別出來的，因此我們再設計Node節點時，應該添加一個IsWord，判斷該節點是否是單詞的結尾。
創建一棵Trie
在創建Trie之前，我們需要先設計Trie的節點類，根據上面說的，每個節點都有若干個指向下個節點的指針，還需要一個isWord來判斷是否是單詞的結尾，代碼實現如下：
//設計Trie的節點類
private class Node{
//判斷是否是一個單詞
public boolean isWord;
//每個節點有若干個指向下個節點的指針
public TreeMap<Character,Node> next;
//有參構造：對該節點進行初始化
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
//無參構造：默認當前節點不是單詞的結尾
public Node(){
this(false);
}
}
現在就讓我們來實現一個Trie
public class Trie {
//設計Trie的節點類
private class Node{
//判斷是否是一個單詞
public boolean isWord;
//每個節點有若干個指向下個節點的指針
public TreeMap<Character,Node> next;
//有參構造：對該節點進行初始化
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
//無參構造：默認當前節點不是單詞的結尾
public Node(){
this(false);
}
}
private Node root;
private int size;
public Trie() {
root = new Node();
size = 0;
}
// 獲得Trie中存儲的單詞數量
public int getSize(){
return size;
}
}
向Trie中添加元素
Trie的添加操作：添加的是一個字符串，要把這個字符串拆成一個一個字符，把這一個一個字符作為一個一個節點，存入Trie中。
//向Trie中添加一個新的單詞word
public void add(String word){
Node cur = root;
for (int i = 0 ;i < word.length(); i++){
//將這個新單詞，拆成一個一個字符
char c = word.charAt(i);
//如果當前節點的若干個子節點中，沒有存儲當前字符的節點，則需要創建一個子節點，存儲當前字符
if (cur.next.get(c) == null){
cur.next.put(c,new Node());
}
cur = cur.next.get(c);
}
//對添加的新單詞遍歷結束後，判斷當前節點是否為單詞的結尾,如果不是我們才對size加一，並且維護當前節點的isWord
if (! cur.isWord){
cur.isWord = true;
size ++;
}
}
Trie的查詢操作
//Tire的查詢操作
public boolean contains(String word){
Node cur = root;
for (int i = 0;i < word.length(); i++){
char c = word.charAt(i);
if (cur.next.get(c) == null ){
return false;
}
cur = cur.next.get(c);
}
return cur.isWord;
}
與查詢類型，我們可以寫一個是否存在以某個單詞為前綴的單詞
//查詢在Trie中是否有單詞以prefix為前綴
public boolean isPrefix(String prefix){
Node cur = root;
for (int i = 0; i < prefix.length(); i++){
char c = prefix.charAt(i);
if (cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return true;
}
對比二分搜索樹和Trie的性能
這裡對比二分搜索樹和Trie的性能，仍然是使用的以添加和統計《傲慢與偏見》這本書為例，關於該測試用例中的文件工具類，和《傲慢與偏見》文檔，請前往我之前寫的 集合和映射 進行獲取。
public static void main(String[] args) {
System.out.println("Pride and Prejudice");
List<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt", words)){
// Collections.sort(words);
long startTime = System.nanoTime();
//使用基於二分搜索樹實現的集合進行添加和查詢操作
BSTSet<String> set = new BSTSet<>();
for(String word: words)
set.add(word);
for(String word: words)
set.contains(word);
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0;
//基於二分搜索樹實現的集合進行添加和查詢操作所花費的時間
System.out.println("Total different words: " + set.getSize());
System.out.println("BSTSet: " + time + " s");
// --- 測試通過Trie通過添加和查詢所需要的時間
startTime = System.nanoTime();
Trie trie = new Trie();
for(String word: words)
trie.add(word);
for(String word: words)
trie.contains(word);
endTime = System.nanoTime();
time = (endTime - startTime) / 1000000000.0;
System.out.println("Total different words: " + trie.getSize());
System.out.println("Trie: " + time + " s");
}
}
通過上面測試代碼可以看出，其實數據量不大的情況下，對於一個隨機字符串的集合，使用二分搜索書和Trie進行添加和查詢操作，差別是不大的，如果我們加入的數據是有序的，這時二分搜索樹就會退化成鏈表，時間複雜度就為O（n），運行效率是很低的，但是Trie並不受影響，我們可以對words進行排序後，在看一下運行結果:
通過上面的測試，可以看出對有序的數據進行添加和查詢操作，差距是特別大的。
leetcode上的問題
我們可以看到leetcode官網上的208好問題，就是實現一個Trie
其實從題目描述中就可以看出，這個問題中的三個方法就是我們實現的add(),contains(),isPrefix()操作，直接將我們寫的代碼改個方法名字提交就可以通過了。
我們再來看一道leetcode上的211號問題：添加與搜索單詞
通過題目描述，我們會發現只是查詢操作和我們實現的Trie有所不同，添加操作沒有發改變。由於字符’.’可以代表任何一個字母，所以我們對於’.’，需要遍歷所有的可能。
public boolean search(String word) {
//遞歸匹配查找
return match(root,word,0);
}
private boolean match(Node node, String word, int index) {
if (index == word.length())
return node.isWord;
char c = word.charAt(index);
if (c != '.'){
if (node.next.get(c) == null)
return false;
return match(node.next.get(c),word,index+1);
}
else {
//如果當前節點的的值為『.』,則需要遍歷當前節點的所有子節點
for (char nextChar : node.next.keySet()) {
if (match(node.next.get(nextChar),word,index+1)){
return true;
}
}
return false;
}
}
代碼提交到leetcode後，就會提示通過了
我們再來看看leetcode上的677號問題：Map Sum Pairs(鍵值映射)
根據題目描述，我們可以理解為：映射中存儲的是單詞和權重值。sum()方法是求得包含這個前綴單詞得權重和
代碼實現如下：
//設計節點類
private class Node{
//單詞的權重值
public int value;
//每個節點都可能有若干個子節點
public TreeMap<Character,Node> next;
public Node(int value){
this.value = value;
next = new TreeMap<>();
}
public Node(){
this(0);
}
}
private Node root;
public MapSum(){
root = new Node();
}
//添加操作和我們實現的字典樹中的添加操作類型
public void insert(String word,int val){
Node cur = root;
for (int i = 0 ; i < word.length() ; i++){
char c = word.charAt(i);
if (cur.next.get(c) == null){
cur.next.put(c,new Node());
}
cur = cur.next.get(c);
}
cur.value = val;
}
//求前綴為prefix的權重和
public int sum(String prefix){
Node cur = root;
for (int i = 0 ; i < prefix.length() ; i++){
char c = prefix.charAt(i);
if ( cur.next.get(c) == null ){
return 0;
}
cur = cur.next.get(c);
}
return sum(cur);
}
private int sum(Node node) {
int res = node.value;
for (char c : node.next.keySet()) {
res += sum(node.next.get(c));
}
return res;
}
leetcode上的提交結果：
