Implement Trie (字典樹)

發表於 2023-03-18 分類於 DSA 閱讀次數：文章字數： 931 所需閱讀時間 ≈ 4 分鐘

前言

今天在寫LeetCode每日一題時遇到208. Implement Trie (Prefix Tree)，之前因為覺得Trie好像很難所以一直不願面對，但這題就是要跟Trie的直球對決了想躲也躲不掉XD，Anyway，看了一下發現Trie其實蠻好理解的，今天就來認識一下Trie，然後看看這一題可以怎麼寫吧！(Python, C++)

Trie 介紹

Trie的中文可以叫做字典樹、字首樹或前綴樹，顧名思義是一種樹狀結構，常被用來檢索文本中的單詞或前綴(prefix)。

字典樹有幾個性質，這裡搭配下方圖片做介紹：

每個節點代表一個字符，並且單字的結尾有標記，舉例來說單字"ten"會依序經過t、e、n三個節點，其中n是結尾(綠色)。
節點是可以被共用的，舉例來說"sun"及"sup"就共用了s、u兩個節點。
葉子節點一定是單字結尾，但非葉節點也可以是結尾，舉例來說"an"及"and"分別是兩個單字，其中n及d都是單字的結尾(綠色)。

trie
字典樹的優點是可以快速查找字符串，且可以按照字典序進行排序。但缺點是需要較大的空間來存儲，且插入和刪除操作相對較慢。

實作 Trie

實作的內容就是一開始提到的LeetCode 208，簡單來說就是要做出初始化、插入、尋找及尋找前綴4個功能，詳細題目可以自己到LeetCode去看。

值得一提的是，Trie 有兩種實作方法，第一個方法相當直覺，就是用指針連結各個節點來模擬出一個樹狀結構；第二個方法則是動態語言限定，我們可以直接用hash table來儲存字符，接下來分別用C++及Python來演示這兩種方法。

方法一: Pointers (C++)

重點

英文字母只有26個，所以可以直接使用array，以index(w-'a')來表示字符。
prefix的部分只要節點存在就OK，但search的部分還要檢查是不是結尾。
另外定義一個struct而不是直接new原本的class，是因為struct的結構比class簡單的多(沒有function)，可以提升執行效率。
使用靜態宣告(array)所以不用擔心memory leak。

struct Node{
  Node* children[26];
  bool is_word = false;
};

class Trie {
public:
    Node* root;
    Trie() {
        root = new Node();
    }

    void insert(string word) {
        Node* curr = root;
        for (char w: word) {
            if(curr->children[w-'a'] == nullptr){
                curr->children[w-'a'] = new Node();
            }
            curr = curr->children[w-'a'];
        }
        curr->is_word = true;
    }

    bool search(string word) {
        Node* curr = root;
        for (char w: word) {
            if(curr == NULL || curr->children[w-'a'] == nullptr){
                return false;
            }
            curr = curr->children[w-'a'];
        }
        return curr->is_word;
    }

    bool startsWith(string prefix) {
        Node* curr = root;
        for (char w: prefix) {
            if(curr->children[w-'a'] == nullptr){
                return false;
            }
            curr = curr->children[w-'a'];
        }
        return true;
    }
};

方法二: Hash Table (Python)

重點

用特殊符號(#)來標記單字結尾。
因為動態語言中的資料型態是動態決定的，所以Hash Table內可以同時儲存不同資料型態(存下一層/存結尾)。

class Trie:
    def __init__(self):
        self._root = {}

    def insert(self, word: str) -> None:
        curr = self._root
        for w in word:
            if w not in curr:
                curr[w] = {}
            curr = curr[w]
        curr["#"] = True
        
    def search(self, word: str) -> bool:
        curr = self._root
        for w in word:
            if w in curr:
                curr = curr[w]
            else:
                return False
        return curr.get("#", False)

    def startsWith(self, prefix: str) -> bool:
        curr = self._root
        for w in prefix:
            if w in curr:
                curr = curr[w]
            else:
                return False
        return True

Trie (字典樹) - Design Add and Search Words Data Structure

結語

Trie的基本觀念說實在還蠻簡單的，難應該是難在之後的應用，之後有機會看能不能更新一些進階的觀念，像是搜尋引擎之類的。

Reference

https://www.youtube.com/watch?v=f48wGD-MuQw

前言

Trie 介紹

實作 Trie

方法一: Pointers (C++)

方法二: Hash Table (Python)

相關文章

結語

Reference