Trie 樹（字典樹）#

應用場景#

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

核心思想#

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

結構特點#

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

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

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

* 表示單詞結尾

Map 實作（彈性字元集）#

每個節點用一個 HashMap<Char, TrieNode> 掛住子節點，並以 isWord 旗標標記單詞結尾。字元集不限大小，適合中文等大字元集。

class TrieNode {
    val children = HashMap<Char, TrieNode>()
    var isWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (c in word) {
            // 查找或插入：一行完成
            node = node.children.getOrPut(c) { TrieNode() }
        }
        node.isWord = true
    }

    fun search(word: String): Boolean {
        val node = findNode(word)
        return node != null && node.isWord
    }

    fun startsWith(prefix: String): Boolean = findNode(prefix) != null

    private fun findNode(s: String): TrieNode? {
        var node = root
        for (c in s) {
            node = node.children[c] ?: return null
        }
        return node
    }
}

Kotlin 技巧：getOrPut(key) { default } 若 key 不存在則建立並放入 default，再回傳——一行搞定「查找或插入」，取代 Python 的 setdefault。

定長陣列實作（限小寫字母）#

字元集固定為 26 個小寫字母時，改用 arrayOfNulls<TrieNode>(26) 直接以 c - 'a' 索引，比 HashMap 更省時間常數。

class TrieNode {
    val children = arrayOfNulls<TrieNode>(26)
    var isWord = false
}

class ArrayTrie {
    private val root = TrieNode()

    fun insert(word: String) {
        var node = root
        for (c in word) {
            val idx = c - 'a'
            if (node.children[idx] == null) {
                node.children[idx] = TrieNode()
            }
            node = node.children[idx]!!
        }
        node.isWord = true
    }

    fun search(word: String): Boolean {
        val node = findNode(word)
        return node != null && node.isWord
    }

    fun startsWith(prefix: String): Boolean = findNode(prefix) != null

    private fun findNode(s: String): TrieNode? {
        var node = root
        for (c in s) {
            val idx = c - 'a'
            node = node.children[idx] ?: return null
        }
        return node
    }
}

這正是實作 Trie ^↗ 的標準解法。

複雜度分析#

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

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

優缺點#

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

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

三大性質#

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

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