什么是Trie字典樹(shù)
Trie 樹(shù)，也叫“字典樹(shù)”或“前綴樹(shù)”。顧名思義，它是一個(gè)樹(shù)形結(jié)構(gòu)。但與二分搜索樹(shù)、紅黑樹(shù)等不同的是，Trie 樹(shù)是一種多叉樹(shù)，即每個(gè)節(jié)點(diǎn)可以有 m 個(gè)子節(jié)點(diǎn)。它是一種專門(mén)處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，用來(lái)解決在一組字符串集合中快速查找某個(gè)字符串的問(wèn)題。
例如，在一個(gè)字典中有 個(gè)條目，如果使用普通的二分搜索樹(shù)（不考慮退化），那么在該字典中查詢指定條目的時(shí)間復(fù)雜度是
，如果有100w個(gè)條目（
），
大約為20。
而如果使用 Trie 樹(shù)的話，查詢每個(gè)條目的時(shí)間復(fù)雜度，和字典中一共有多少條目無(wú)關(guān)。時(shí)間復(fù)雜度為 ，其中
為查詢單詞的長(zhǎng)度，而且絕大多數(shù)的單詞長(zhǎng)度都小于 10。由此可見(jiàn)，使用 Trie 樹(shù)實(shí)現(xiàn)字符串查詢，特別是只查詢其前綴的情況下，是比普通的樹(shù)形結(jié)構(gòu)效率要更高的。
那么 Trie 樹(shù)是如何做到其查詢時(shí)間復(fù)雜度與條目數(shù)量無(wú)關(guān)的呢？這是因?yàn)?Trie 樹(shù)的本質(zhì)，就是利用字符串之間的公共前綴，將重復(fù)的前綴合并在一起。例如，我們將：how，hi，her，hello，so，see 這6個(gè)字符串構(gòu)造成一顆 Trie 樹(shù)。那么，最后構(gòu)造出來(lái)的就是下面這個(gè)圖中的樣子：
其中，根節(jié)點(diǎn)不包含任何信息。每個(gè)節(jié)點(diǎn)表示一個(gè)字符串中的字符，從根節(jié)點(diǎn)到紅色節(jié)點(diǎn)的一條路徑表示一個(gè)字符串（注意：紅色節(jié)點(diǎn)并不都是葉子節(jié)點(diǎn)）。
為了更容易理解 Trie 樹(shù)是怎么構(gòu)造出來(lái)的，我們可以看如下 Trie 樹(shù)構(gòu)造的分解過(guò)程。構(gòu)造過(guò)程的每一步，都相當(dāng)于往 Trie 樹(shù)中插入一個(gè)字符串。當(dāng)所有字符串都插入完成之后，Trie 樹(shù)就構(gòu)造好了：
當(dāng)我們?cè)?Trie 樹(shù)中查找一個(gè)字符串的時(shí)候，比如查找字符串“her”，那我們將要查找的字符串分割成單個(gè)的字符 h，e，r，然后從 Trie 樹(shù)的根節(jié)點(diǎn)開(kāi)始匹配。如圖所示，綠色的路徑就是在 Trie 樹(shù)中匹配的路徑：
之前有提到過(guò)， Trie 樹(shù)是多叉樹(shù)，那么這個(gè)“多叉”是怎么體現(xiàn)的呢？通常來(lái)講，如果你只針對(duì)小寫(xiě)字母構(gòu)造一棵 Trie 樹(shù)，就像我們上面的例子，那么每個(gè)節(jié)點(diǎn)中使用一個(gè)長(zhǎng)度為26的數(shù)組來(lái)表示其多個(gè)子節(jié)點(diǎn)即可。如下所示：
class Node {
char data;
Node children[26];
}
而如果我們的需求不僅僅是只包含小寫(xiě)字母，希望這是一棵通用的 Trie 樹(shù)，那么就需要設(shè)計(jì)一個(gè)能動(dòng)態(tài)變化的子節(jié)點(diǎn)容器，使得每個(gè)節(jié)點(diǎn)有若干指向下個(gè)節(jié)點(diǎn)的指針。例如，我們可以使用一個(gè) Map 來(lái)實(shí)現(xiàn)，如下所示：
class Node {
boolean isWord; // 標(biāo)識(shí)是否是單詞的結(jié)尾
Map<Character, Node> next;
}
Trie字典樹(shù)基礎(chǔ)代碼
通過(guò)以上的介紹，我們已經(jīng)了解到了 Trie 樹(shù)的基本概念。接下來(lái)，讓我們實(shí)現(xiàn)一下 Trie 樹(shù)的基礎(chǔ)功能代碼，從代碼上對(duì) Trie 樹(shù)有個(gè)直觀的認(rèn)識(shí)。具體代碼如下：
package tree;
import java.util.Map;
import java.util.TreeMap;
/**
* Trie樹(shù)
*
* @author 01
* @date 2021-01-28
**/
public class TrieTree {
private final Node root;
private int size;
/**
* Trie樹(shù)中每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)
*/
private static class Node {
/**
* 標(biāo)識(shí)是否是單詞的結(jié)尾
*/
private boolean isWord;
/**
* 使用Map來(lái)實(shí)現(xiàn)動(dòng)態(tài)存儲(chǔ)多個(gè)子節(jié)點(diǎn)
*/
private final Map<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
public TrieTree() {
root = new Node();
size = 0;
}
/**
* 獲取Trie中存儲(chǔ)的單詞數(shù)量
*/
public int getSize() {
return size;
}
/**
* 向Trie中添加一個(gè)新的單詞word
*/
public void add(String word) {
Node current = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (current.next.get(c) == null) {
// 沒(méi)有與之對(duì)應(yīng)的子節(jié)點(diǎn)，創(chuàng)建一個(gè)新的子節(jié)點(diǎn)
current.next.put(c, new Node());
}
current = current.next.get(c);
}
if (!current.isWord) {
// 添加的是新的單詞，標(biāo)識(shí)該節(jié)點(diǎn)是單詞的結(jié)尾
current.isWord = true;
size++;
}
}
}
Trie字典樹(shù)的查詢
Trie 字典樹(shù)的查詢主要就是查詢某個(gè)單詞是否存在于 Trie 中，其主要邏輯與 add 方法基本上是一樣的。代碼如下：
/**
* 查詢單詞word是否在Trie中
*/
public boolean contains(String word){
Node current = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (current.next.get(c) == null) {
return false;
}
current = current.next.get(c);
}
// 只有當(dāng)最后一個(gè)字母所對(duì)應(yīng)的節(jié)點(diǎn)標(biāo)識(shí)了是一個(gè)單詞的結(jié)尾，
// 才能認(rèn)為這個(gè)單詞存在于Trie中
return current.isWord;
}
Trie字典樹(shù)的前綴查詢
相比于查詢某個(gè)單詞是否存在 Trie 樹(shù)中，前綴查詢的使用范圍更廣，也是 Trie 樹(shù)中的主要查詢操作。通過(guò)前綴查詢，我們可以實(shí)現(xiàn)像搜索引擎那樣的搜索關(guān)鍵詞提示功能。實(shí)現(xiàn)前綴查詢的代碼與查詢某個(gè)單詞基本上是一樣的，如下所示：
/**
* 查詢是否在Trie中有單詞以prefix為前綴
*/
public boolean hasPrefix(String prefix) {
Node current = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (current.next.get(c) == null) {
return false;
}
current = current.next.get(c);
}
return true;
}
Trie字典樹(shù)和簡(jiǎn)單的模式匹配
接下來(lái)，我們嘗試使用Trie字典樹(shù)來(lái)解決LeetCode上的一個(gè)簡(jiǎn)單模式匹配的問(wèn)題，該問(wèn)題的編號(hào)是211：
關(guān)于這個(gè)問(wèn)題的詳細(xì)內(nèi)容，可以查看以上鏈接，這里就不做贅述了。對(duì)于該問(wèn)題，具體的實(shí)現(xiàn)代碼如下：
package tree.trie;
import java.util.Map;
import java.util.TreeMap;
/**
* Leetcode 211. Add and Search Word - Data structure design
* https://leetcode.com/problems/add-and-search-word-data-structure-design/description/
*
* @author 01
*/
public class WordDictionary {
private static class Node {
private boolean isWord;
private final Map<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private final Node root;
/**
* Initialize your data structure here.
*/
public WordDictionary() {
root = new Node();
}
/**
* Adds a word into the data structure.
*/
public void addWord(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);
}
cur.isWord = true;
}
/**
* Returns if the word is in the data structure.
* A word could contain the dot character '.' to represent any one letter.
*/
public boolean search(String word) {
return match(root, word, 0);
}
private boolean match(Node node, String word, int index) {
// 遞歸到底了，返回該節(jié)點(diǎn)是否是一個(gè)單詞
if (index == word.length()) {
return node.isWord;
}
char c = word.charAt(index);
if (c != '.') {
if (node.next.get(c) == null) {
return false;
}
// 遞歸繼續(xù)匹配下一個(gè)字母
return match(node.next.get(c), word, index + 1);
} else {
// 包含通配符，需要遍歷匹配全部子節(jié)點(diǎn)
for (char nextChar : node.next.keySet()) {
if (match(node.next.get(nextChar), word, index + 1)) {
return true;
}
}
return false;
}
}
}
Trie字典樹(shù)和字符串映射
最后，我們?cè)賮?lái)解決一個(gè)LeetCode上的677號(hào)問(wèn)題，該問(wèn)題的鏈接如下：
對(duì)于該問(wèn)題我們就是要將Trie字典樹(shù)作為一個(gè)映射，每個(gè)單詞就是一個(gè) key，對(duì)應(yīng)著一個(gè) value，該 value 只存在于單詞最后一個(gè)字母對(duì)應(yīng)的節(jié)點(diǎn)。如下圖所示：
有了這個(gè)形象的概念后，代碼編寫(xiě)起來(lái)就簡(jiǎn)單了，所以也建議各位實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)時(shí)可以嘗試多畫(huà)圖。對(duì)于該問(wèn)題的具體實(shí)現(xiàn)代碼如下：
package tree.trie;
import java.util.Map;
import java.util.TreeMap;
/**
* 鍵值映射
* https://leetcode-cn.com/problems/map-sum-pairs/
*
* @author 01
*/
public class MapSum {
private static class Node {
private int value;
private final Map<Character, Node> next;
public Node(int value) {
this.value = value;
next = new TreeMap<>();
}
public Node() {
this(0);
}
}
private final Node root;
/**
* Initialize your data structure here.
*/
public MapSum() {
root = new Node();
}
public void insert(String key, int val) {
Node cur = root;
for (int i = 0; i < key.length(); i++) {
char c = key.charAt(i);
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
cur.value = val;
}
public int sum(String prefix) {
Node cur = root;
// 找到這個(gè)前綴最后一個(gè)字母所對(duì)應(yīng)的節(jié)點(diǎn)
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);
}
// 對(duì)該節(jié)點(diǎn)所有路徑下的子節(jié)點(diǎn)的value進(jìn)行求和
return sum(cur);
}
private int sum(Node node) {
int res = node.value;
// 遍歷所有子節(jié)點(diǎn)
for (char c : node.next.keySet()) {
// 對(duì)每個(gè)子節(jié)點(diǎn)路徑上的value進(jìn)行遞歸求和
res += sum(node.next.get(c));
}
return res;
}
}
