Tire

需求分析

如何判斷一堆不重復(fù)的字符串是否以某個(gè)前綴開頭？

• 用 Set\Map 存儲(chǔ)字符串（不重復(fù)）
• 遍歷所有字符串進(jìn)行判斷
• 缺點(diǎn)：時(shí)間復(fù)雜度 O(n)

有沒有更優(yōu)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)前綴搜索？

Tire（和 Tree 同音）

簡介

• Trie 也叫做字典樹、前綴樹 (Prefix Tree)、單詞查找樹。
• Trie 搜索字符串的效率主要跟字符串的長度有關(guān)。

假設(shè)使用 Trie 存儲(chǔ) cat、dog、doggy、does、cast、add 六個(gè)單詞，結(jié)果如下所示

接口設(shè)計(jì)

有兩種設(shè)計(jì)方案：

1. 第一種僅僅是存儲(chǔ)字符串。（像 set 集合）
2. 第二種是存儲(chǔ)字符串的同時(shí)可以再存儲(chǔ)一個(gè) value（像 map 接口）

分析：

第二種設(shè)計(jì)方案更為通用，比如說我們要做一個(gè)通訊錄，以某個(gè)人的姓名作為 key，然后以他的詳細(xì)信息作為 value（其他電話號(hào)碼、郵箱、生日等各種詳細(xì)信息）

public interface Trie <V> {int size(); boolean isEmpty(); void clear(); boolean contains(String str); V add(String str, V value); V remove(String str); boolean starswith(String prefix);
}

Node 設(shè)計(jì)

孩子節(jié)點(diǎn)集合解析（HashMap<Character, Node<V>> children;）：

• key 相當(dāng)于代表的是路徑值，Character 字符類型可以是英文也可以是中文
• value 是嵌套了當(dāng)前節(jié)點(diǎn)下的所有子節(jié)點(diǎn)，方便后面節(jié)點(diǎn)值尋找
• word：true 為已存儲(chǔ)單詞（紅色），false 為非單詞（藍(lán)色）

    /*** Trie 中的節(jié)點(diǎn)類，包含父節(jié)點(diǎn)、孩子節(jié)點(diǎn)集合、字符、值以及表示是否為一個(gè)完整單詞的標(biāo)志。** @param <V> 值的類型*/private static class Node<V> {Node<V> parent; // 父節(jié)點(diǎn)HashMap<Character, Node<V>> children; // 孩子節(jié)點(diǎn)集合Character character; // 字符，為刪除做準(zhǔn)備V value; // 節(jié)點(diǎn)對(duì)應(yīng)的值，也就是整個(gè)單詞boolean word; // 是否為單詞的結(jié)尾（是否為一個(gè)完整的單詞）/*** 構(gòu)造函數(shù)，初始化節(jié)點(diǎn)時(shí)需要指定父節(jié)點(diǎn)。(在添加節(jié)點(diǎn)時(shí)用到）** @param parent 父節(jié)點(diǎn)*/public Node(Node<V> parent) {this.parent = parent;}}

完整代碼實(shí)現(xiàn)附注釋

/*** Trie（字典樹）數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)字符串集合，支持添加、查詢、刪除等操作。** @param <V> 值的類型*/
public class Trie<V> {/** Trie 中存儲(chǔ)的單詞數(shù)量 */private int size;/** 根節(jié)點(diǎn) */private Node<V> root;/*** Trie 中的節(jié)點(diǎn)類，包含父節(jié)點(diǎn)、孩子節(jié)點(diǎn)集合、字符、值以及表示是否為一個(gè)完整單詞的標(biāo)志。** @param <V> 值的類型*/private static class Node<V> {Node<V> parent; // 父節(jié)點(diǎn)HashMap<Character, Node<V>> children; // 孩子節(jié)點(diǎn)集合Character character; // 字符，為刪除做準(zhǔn)備V value; // 節(jié)點(diǎn)對(duì)應(yīng)的值，也就是整個(gè)單詞boolean word; // 是否為單詞的結(jié)尾（是否為一個(gè)完整的單詞）/*** 構(gòu)造函數(shù)，初始化節(jié)點(diǎn)時(shí)需要指定父節(jié)點(diǎn)。(在添加節(jié)點(diǎn)時(shí)用到）** @param parent 父節(jié)點(diǎn)*/public Node(Node<V> parent) {this.parent = parent;}}/*** 獲取 Trie 中存儲(chǔ)的單詞數(shù)量。** @return Trie 中存儲(chǔ)的單詞數(shù)量*/public int size() {return size;}/*** 判斷 Trie 是否為空。** @return 如果 Trie 為空，則返回 true；否則返回 false*/public boolean isEmpty() {return size == 0;}/*** 清空 Trie，將單詞數(shù)量重置為 0。*/public void clear() {size = 0;root = null;}/*** 根據(jù)指定的鍵獲取對(duì)應(yīng)的值。** @param key 鍵* @return 如果鍵存在且是一個(gè)完整的單詞，則返回對(duì)應(yīng)的值；否則返回 null*/public V get(String key) {Node<V> node = node(key);return (node != null && node.word) ? node.value : null;}/*** 判斷 Trie 是否包含指定的鍵。** @param key 鍵* @return 如果 Trie 包含指定的鍵且是一個(gè)完整的單詞，則返回 true；否則返回 false*/public boolean contains(String key) {Node<V> node = node(key);return node != null && node.word;}/*** 添加鍵值對(duì)到 Trie 中。如果鍵已經(jīng)存在，則更新對(duì)應(yīng)的值；否則新增一個(gè)單詞。** @param key   鍵* @param value 值* @return 如果添加的鍵已經(jīng)存在，則返回對(duì)應(yīng)的舊值；否則返回 null*/public V add(String key, V value) {keyCheck(key);// 創(chuàng)建根節(jié)點(diǎn)if (root == null) {root = new Node<>(null);}// 獲取 Trie 根節(jié)點(diǎn)Node<V> node = root;// 獲取鍵的長度int len = key.length();// 遍歷鍵的每個(gè)字符for (int i = 0; i < len; i++) {// 獲取當(dāng)前字符char c = key.charAt(i);// 判斷當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)集合是否為空boolean emptyChildren = (node.children == null);// 獲取當(dāng)前字符對(duì)應(yīng)的孩子節(jié)點(diǎn)Node<V> childNode = emptyChildren ? null : node.children.get(c);// 如果當(dāng)前字符對(duì)應(yīng)的孩子節(jié)點(diǎn)為空，說明該字符在當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)集合中不存在if (childNode == null) {// 創(chuàng)建新的孩子節(jié)點(diǎn)，并將其加入到當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)集合中childNode = new Node<>(node);childNode.character = c;// 判斷孩子節(jié)點(diǎn)集合是否為空的同時(shí)，避免了每次都要?jiǎng)?chuàng)建新的 HashMap 對(duì)象，提高了效率node.children = emptyChildren ? new HashMap<>(16) : node.children;node.children.put(c, childNode);}// 將當(dāng)前節(jié)點(diǎn)移動(dòng)到其對(duì)應(yīng)的孩子節(jié)點(diǎn)上，繼續(xù)下一層的遍歷node = childNode;}// 1 - 已經(jīng)存在這個(gè)單詞, 覆蓋, 返回舊值if (node.word) {V oldValue = node.value;node.value = value;return oldValue;}// 2 - 不存在這個(gè)單詞, 新增這個(gè)單詞node.word = true;node.value = value;size++;return null;}/*** 移除 Trie 中的指定鍵。如果鍵存在且是一個(gè)完整的單詞，將其從 Trie 中移除。** @param key 鍵* @return 如果鍵存在且是一個(gè)完整的單詞，則返回對(duì)應(yīng)的值；否則返回 null*/public V remove(String key) {Node<V> node = node(key);// 如果不是單詞結(jié)尾，不用作任何處理if (node == null || !node.word) {return null;}size--;V oldValue = node.value;// 如果還有子節(jié)點(diǎn)if (node.children != null && !node.children.isEmpty()) {node.word = false;node.value = null;return oldValue;}// 沒有子節(jié)點(diǎn)Node<V> parent = null;while ((parent = node.parent) != null) {parent.children.remove(node.character);if (parent.word || !parent.children.isEmpty()) {break;}node = parent;}return oldValue;}/*** 判斷 Trie 是否包含指定前綴。** @param prefix 前綴* @return 如果 Trie 包含指定前綴，則返回 true；否則返回 false*/public boolean startsWith(String prefix) {return node(prefix) != null;}/*** 根據(jù)傳入字符串，找到最后一個(gè)節(jié)點(diǎn)。* 例如輸入 dog* 找到 g** @param key 鍵* @return 如果鍵存在，則返回對(duì)應(yīng)的節(jié)點(diǎn)；否則返回 null*/private Node<V> node(String key) {keyCheck(key);Node<V> node = root;int len = key.length();for (int i = 0; i < len; i++) {if (node == null || node.children == null || node.children.isEmpty()) {return null;}char c = key.charAt(i);node = node.children.get(c);}return node;}/*** 檢查鍵是否合法，不允許為空。** @param key 鍵*/private void keyCheck(String key) {if (key == null || key.length() == 0) {throw new IllegalArgumentException("key must not be empty");}}
}

總結(jié)

1. Trie 的優(yōu)點(diǎn)：搜索前綴的效率主要跟前綴的長度有關(guān)

2. Trie 的缺點(diǎn)：需要耗費(fèi)大量的內(nèi)存（一個(gè)字符一個(gè)節(jié)點(diǎn)），因此還有待改進(jìn)

3. 更多 Trie 相關(guān)的數(shù)據(jù)結(jié)構(gòu)和算法

   • Double-array Trie、Suffix Tree（后綴樹）、Patricia Tree、Crit-bit Tree、AC 自動(dòng)機(jī)