Tire

需求分析

如何判斷一堆不重復的字符串是否以某個前綴開頭？

• 用 Set\Map 存儲字符串（不重復）
• 遍歷所有字符串進行判斷
• 缺點：時間復雜度 O(n)

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

Tire（和 Tree 同音）

簡介

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

假設使用 Trie 存儲 cat、dog、doggy、does、cast、add 六個單詞，結果如下所示

接口設計

有兩種設計方案：

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

分析：

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

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 設計

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

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

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

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

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

總結

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

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

3. 更多 Trie 相關的數(shù)據(jù)結構和算法

   • Double-array Trie、Suffix Tree（后綴樹）、Patricia Tree、Crit-bit Tree、AC 自動機