跳到主要內容
Jasonmel Online

資料結構

資料怎麼排，決定了哪些操作便宜

主題 · 字首樹

字首樹

依字元一層一層往下分岔的樹：找一個字的成本只和字的長度有關，和收了多少字無關，還能列出所有共同字首的字。

·cardettdogtteanoreeiey
走過的字首停下的節點沒路了字首底下收集到的到這裡是一個字

每個節點代表一個字首，往下一層就多一個字元；有標記（實心）的節點表示「到這裡是一個完整的字」。共用字首的字共用同一條路，例如 car、card、care、cart。

字
14
節點（含根）
23
這次往下走幾步
–
這次走訪幾個節點
–
亮起來的是這一步執行的程式碼
class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}
 
class Trie {
  root = new TrieNode();
 
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      let next = node.children.get(ch);
      if (!next) {
        next = new TrieNode();
        node.children.set(ch, next);
      }
      node = next;
    }
    node.isWord = true;
  }
 
  has(word: string): boolean {
    return this.find(word)?.isWord ?? false;
  }
 
  withPrefix(prefix: string): string[] {
    const start = this.find(prefix);
    const out: string[] = [];
    if (!start) return out;
    const walk = (node: TrieNode, sofar: string) => {
      if (node.isWord) out.push(sofar);
      const letters = [...node.children.keys()].sort();
      for (const ch of letters) walk(node.children.get(ch)!, sofar + ch);
    };
    walk(start, prefix);
    return out;
  }
 
  private find(prefix: string): TrieNode | undefined {
    let node = this.root;
    for (const ch of prefix) {
      const next = node.children.get(ch);
      if (!next) return undefined;
      node = next;
    }
    return node;
  }
}

模型假設與範圍

  • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

  • 要問字首：自動完成、輸入法候選字、「所有以 /api/users 開頭的路由」。
  • 要找「最長的相符字首」：路由器查 IP 位址該往哪送、URL 路由比對。

和其他主題的關係

語言內建的版本

Map<string, TrieNode>

沒有內建的字首樹。慣用寫法是每個節點一個 Map，從字元對到子節點，再加一個「這裡是一個字的結尾」的旗標。

操作寫法成本
插入一個字trie.insert("apple")O(L)
整個字在不在trie.search("app")O(L)
有沒有這個字首trie.startsWith("ap")O(L)
class TrieNode {
  children = new Map<string, TrieNode>();
  end = false;
}
 
class Trie {
  root = new TrieNode();
 
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.end = true;
  }
 
  walk(prefix: string): TrieNode | null {
    let node = this.root;
    for (const ch of prefix) {
      const next = node.children.get(ch);
      if (!next) return null;
      node = next;
    }
    return node;
  }
 
  search(word: string): boolean {
    return this.walk(word)?.end === true;
  }
 
  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;
  }
}
 
const trie = new Trie();
trie.insert("app");
trie.insert("apple");
trie.insert("bat");
trie.search("app");                // → true
trie.search("ap");                 // → false
trie.startsWith("ap");             // → true
trie.startsWith("c");              // → false
[...trie.root.children.keys()];    // → ["a", "b"]
trie.insert("😀");
trie.root.children.has("😀");      // → true

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

  • 每個操作只跟字的長度 L 有關，跟存了多少個字無關。代價是記憶體：每個字元一個節點，每個節點一個 Map。
  • for (const ch of word) 依 Unicode code point 走，emoji 是一個字元；用 word[i] 會把它拆成兩個 UTF-16 code unit。
  • 也可以用一般物件 {} 當 children，但 "constructor"、"__proto__" 這類鍵會撞到原型上的屬性，Map 沒有這個問題。

時間與空間複雜度（Big O）

操作平均最差
插入（L = 字的長度）
和字典裡有幾個字無關
O(L)O(L)
查一個字O(L)O(L)
列出字首底下的字
P 是字首長度，K 是底下的節點數
O(P + K)O(P + K)
刪除
取消標記，再往上刪掉沒用的節點
O(L)O(L)

空間：O(N·L)，N 個字、平均長度 L：最差每個字元一個節點，共用字首越多越省

Big O 實測：n 變大時步數怎麼長

數的是：隨機產生的 4–10 個字母的字；n 是字典裡的字數

Big On = 1,000n = 5,000n = 25,000成長倍數：實測（理論）
字首樹：查一個字走幾步O(1)7.07.07.0×1.0 (×1.0)
雜湊集合：答一次字首查詢要檢查幾個字O(n)1,0005,00025,000×25 (×25)
字首樹：平均每個字幾個節點O(1)5.55.04.5×0.8 (×1.0)

字典變大，查一個字的步數完全不變，只看字有多長；每個字平均用的節點反而略減，因為共用的字首變多了。

和其他做法比

字首樹雜湊集合
查一個字在不在走 7.0 步（字的長度）算一次雜湊（也要讀過每個字元）＋約 1 次比較
列出「jb」開頭的字走訪 67 個節點，找到 18 個檢查全部 10,000 個字
記憶體48,035 個節點，每個都有一張子節點表10,000 筆

10,000 個隨機產生的 4–10 個字母的字，實際建好兩種結構量出來的。查單一個字兩者差不多；問字首時雜湊集合沒有捷徑，只能全部看一遍。代價是字首樹的節點多，記憶體用得兇。

真實世界裡的它

  • 搜尋框的自動完成、手機鍵盤和中文輸入法的候選字。
  • 網路路由表的最長字首比對（Linux 用壓縮過的字首樹 LC-trie，Level-Compressed trie）；Web 框架的路由器（例如 Go 的 httprouter 用 radix tree）。

取捨與陷阱

  • 每個節點都有一張子節點表，記憶體用量可能比字本身大好幾倍；實務上常把只有一個子節點的鏈壓縮成一段（radix tree）。
  • 只查完整的字、不需要字首時，雜湊集合更簡單也更省記憶體。
  • 字母表很大時（Unicode、中文），子節點不能用固定大小的陣列，要改用雜湊表或排序過的陣列。

LeetCode 練習