Trie 樹（字典樹）#

應用場景#

搜尋引擎的自動補全功能：輸入 “bit” 後，推薦 “bitcoin”、“bitmex” 等。

核心思想#

利用公共前綴：減少比較次數和儲存空間
空間換時間：用樹狀結構加速查詢

結構特點#

特點	說明
根節點為空	不儲存字元
路徑代表字串	從根到某節點的路徑組成單詞
結尾標記	區分「完整單詞」和「僅為前綴」

儲存單詞：tea, ten, to, inn

        root
       /    \
      t      i
     /|\     |
    e o *    n
   /|        |
  a n *      n
  *          *

* 表示單詞結尾

Python 實現：巢狀字典#

class Trie:
    def __init__(self):
        self.root = {}
        self.end_mark = '#'

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_mark] = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end_mark in node

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

Python 技巧：setdefault(key, default) 若 key 不存在則設為 default 並返回。

Java 實現：陣列結構#

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord = false;
}

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isWord;
    }

    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }

    private TrieNode findNode(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}

複雜度分析#

操作	時間複雜度
插入	O(m)，m 為單詞長度
搜尋	O(m)
前綴查詢	O(m)

空間複雜度：O(字元集大小 × 總節點數)

優缺點#

優點	缺點
查詢快 O(m)	空間消耗大
支援前綴匹配	字元集大時更浪費
方便擴展（如詞頻統計）	實現比雜湊表複雜

空間問題：若字元集很大（如中文），每個節點的 children 陣列會很大。
優化方案：
雙陣列 Trie (Double-Array Trie)
三元搜尋樹 (Ternary Search Tree)

三大性質#

根節點為空
路徑即字串：從根到節點的路徑字元連接 = 該節點代表的字串
子節點互異：同一節點的子節點代表不同字元

核心價值：Trie 的查詢時間只與單詞長度相關，與字典大小無關！