# [資演] Trie

###### tags: `資演`

## 什麼是 trie？
Trie（發音為「踹」或「tree」），又稱為字典樹、字首樹、前綴樹、單詞搜尋樹，是一種很特別的樹狀資料結構。規則為將單字拆成一個一個字元，每個字元代表一個節點，依照字元在單字中的順序往下長成一棵樹。注意根節點上是沒有字元的，代表空字串是所有字串的共同前綴。


## 性質
與二元搜尋樹、heap 等基於 key 和 value 來儲存資料的資料結構不同，字典樹的建立利用到字串的特性，利用每個字串的共同前綴（common prefix）當儲存依據，並以此來節省儲存空間以及加速搜尋時間。

Trie 利用樹狀結構，每個節點代表一個字元，最大分支度為可能出現的字母總數。一個子節點分別代表字串的下個字母，而整棵樹的高度則為最長字串的長度加上1。

從根節點往下走訪到的每個節點都可能代表一個字串，不一定僅限於葉節點，而每個字串的共同前綴都只會儲存一次。我們可以在節點上維護一個變數，指出該節點是否為一個字串的結尾。有著共同前綴的字串們會被擺在一起，並從最長共同前綴以下才會開始分歧。也就是說，最長共同前綴發生最近共同祖先（Lowest Common Ancestor, LCA）上。

## Trie 上的操作
[[LeetCode] 208. Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)

我們可以先建立一個`TrieNode`類別，用來建立trie上的節點：

class TrieNode:
    def __init__(self):
        self.is_word = False
        self.children = {}

其中，`is_word`是用來指出該節點是否為一個字串的結尾的變數，而`children`則是用來儲存子節點的dict，其中key是子節點上的字元，value是子節點的`TrieNode`。

接著我們建立一個Trie類別，並把`root`初始化為根節點：

class Trie:
    def __init__(self):
        self.root = TrieNode()

### 插入
插入一個新的字串到trie上非常簡單。只要從`root`處開始查找，沿著每個字元連接到下一個`TrieNode`，並且如果節點尚未建立就將其建立，走到底後，將`is_word`設為`True`，就完成了。其程式碼如下：

def insert(self, word):
    node = self.root
    for c in word:
        if c not in node.children:
            node.children[c] = TrieNode()
        node = node.children[c]
    node.is_word = True

### 查詢
要尋找一個特定的字串有沒有在trie裡面出現過也非常簡單，和插入時一樣從`root`開始，沿著每個子節點往下走，但遇到若碰到無法匹配的狀況，不必建立節點，可直接回傳`False`。當走到代表要尋找的字串的最後一個字元的節點時，再依據該節點的`is_word`的狀態來判斷要回傳`True`還是`False`。其程式碼如下：

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

### 檢查前綴（prefix）
給定一個前綴，我們要檢查trie上有沒有以該前綴開始的字串。這個過程跟查詢很像，但只要能走到，就回傳`True`，不必檢查`is_word`的狀態。其程式碼如下：

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

我們可以發現，trie的這三項操作都有類似的步驟，其實也就是trie的尋訪。

Trie的優點是運作速度非常快，且容易實作，但缺點是非常耗費記憶體。

## Follow up
* 如果要在trie上刪除一個字串，該怎麼做？
* 如果要對trie上的字串按照字典順序來排序，要怎麼做？