---
tags: data structure
---
# 資料結構筆記 - Trie
如果今天想要實作如 google 搜尋列中的自動補完功能,通常會先有一個字典結構存放關鍵字,
Trie 是一種樹狀結構也稱為字典樹,用以在大量字串中快速找尋是否存在該字串。此外,Trie 也有人叫前綴樹,因為它是由字串間相同的前綴文字組成。
一個典型的 Trie 如下:

如果我們順著 Root 往下走,每次隨著節點走到 Leaf 時都可以得到一個字串,如上圖我們可以拼出 *CAR*、*CAT*、*DOT* 3 個字串。其中 Trie 的 Root 節點是不存放文字的。
所以今天如果要確認某個字串是否存在於我們的字典裡,只要依序將該字串從頭開始從 Trie 的 Root 出發,只要相同,我們就取出下個文字看看是否和下個子節點相同,一直到該字串沒有文字可以取出來比對就表示存在,如果中途有不同的子節點或者是已經走到 Leaf 但該字串尚未比對完就表示不存在字典中。
比方今天我們用 *CA* 比對,先從 *C* 開始,第一步有節點 **C** 和 *C* 相同,所以我們接著取出 *A* 和 **C** 的子節點比對,而 **C** 的子節點是 **A** 也相同,這時我們要比對的字串已經到尾巴了,所以表示 *CA* 存在於字典中。
如果是用 *CARD* 比對,一樣從 *C* 開始,和節點 **C** 相同,接著 *A* 和 **C** 的子節點 **A** 相同,然後 *R* 和 **A** 的子節點 **R** 相同,但此時 **R** 沒有子節點已經走到 Leaf,但還有 *D* 尚未比對,所以我們知道 *CARD* 不存在字典中。
實作時的 `Node` 內部以 Java 為例:
```java=
class Node {
Map<Character, Node> children;
boolean isWord;
}
```
`children` 存放子節點文字和其 reference,而 `isWord` 標示走到這個節點時是否已經組成之前插入過的文字。
###### Java
```java=
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
class Node {
Map<Character, Node> children = new HashMap<>();
boolean isWord = false;
}
public class Trie {
private Node root;
public Trie() {
root = new Node();
}
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
Node currentNode = root;
for (int i = 0; i < word.length(); i++) {
Character c = word.charAt(i);
Map<Character, Node> children = currentNode.children;
// 如果子節點有此字元,則不需新增節點
if (children.get(c) != null) {
currentNode = children.get(c);
} else {
// 否則就在目前的節點下新增此字元的子節點
currentNode = new Node();
children.put(c, currentNode);
}
}
// 遍歷到最後一個字元時,將該節點的 isWord 標示為 true
// 表示如果從 root 走到這個節點時,目前組合的字串是之前插入過的
currentNode.isWord = true;
}
public boolean search(String word) {
if (word == null || word.length() == 0) {
return false;
}
if (root.children.size() == 0) {
return false;
}
// 從 root 出發
Node currentNode = root;
for (int i = 0; i < word.length(); i++) {
// 取出這個字元對應的子節點
currentNode = currentNode.children.get(word.charAt(i));
// 如果沒有子節點表示 Trie 中沒有這個字串
if (currentNode == null) {
return false;
}
}
// 遍歷到最後一個字元時則檢查該節點是否標為 isWord
// 如果為 true 表示之前有插入過相同的字串
// 如果為 false 表示只是剛好前綴和欲找尋的字串相同
return currentNode.isWord;
}
public void display() {
Node currentNode = root;
display("", currentNode);
}
// 使用遞迴遍歷整個 Trie,顯示目前儲存的字串
private void display(String word, Node currentNode) {
if (currentNode.isWord) {
System.out.println("含有: " + word);
}
// 如果已經到 leaf, 則回到上一層, 所以組好的字串要減去最後一個字
if (currentNode.children == null || currentNode.children.size() == 0) {
word = word.substring(0, word.length() - 1);
return;
}
Set<Character> keySet = currentNode.children.keySet();
Iterator<Character> iterator = keySet.iterator();
while (iterator.hasNext()) {
Character c = iterator.next();
word += c;
display(word, currentNode.children.get(c));
// 執行到這裡表示這個 Node 的子樹已經遍歷完, 所以要換下個 Node
// 因此目前的字串要減掉這次遍歷到的 Node 包含的字, 也就是最後一個字
word = word.substring(0, word.length() - 1);
}
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("test");
trie.insert("MyPhone");
trie.insert("測試中文");
trie.insert("te");
trie.display();
System.out.println("含有 te? " + trie.search("te"));
System.out.println("含有 test? " + trie.search("test"));
System.out.println("含有 My? " + trie.search("My"));
System.out.println("含有 myPhone? " + trie.search("myPhone"));
System.out.println("含有 測試中文? " + trie.search("測試中文"));
System.out.println("含有 測試? " + trie.search("測試"));
}
}
```
###### 輸出結果
```
含有: te
含有: test
含有: 測試中文
含有: MyPhone
含有 te? true
含有 test? true
含有 My? false
含有 myPhone? false
含有 測試中文? true
含有 測試? false
```
參考資料:
1. https://leetcode.com/articles/implement-trie-prefix-tree/#